Бинарное дерево｜Go Theme Month

Go

[Может] чистить Golang тематические проблемы обучения, чем играть в игру намного лучше, становится сильнее чувство выполненного долга, вопрос кисти каждый день, упражнения 30 минут в день, восемь пакетов пресса, и другие производители предлагают.

😄

 \color{red}{~}

Я считаю, что если вы сталкиваетесь с этим вопросом в интервью, то он должен быть логически ясным, правильно сформулированным и разорванным по рукам.

Там должно быть больше, чем часть интервьюируемых.

Друзья, которые не знакомы с деревьями, могут взглянуть на предыдущие базовые обучающие вопросы!

leetcode 106. Построение бинарного дерева из последовательностей обхода в прямом и обратном порядке.

Построить бинарное дерево на основе обхода дерева в упорядоченном и обратном порядке.

Уведомление:

Можно считать, что в дереве нет повторяющихся элементов.

Например, учитывая

Порядок обхода в порядке = [9,3,15,20,7]

Постпорядок обхода постпорядка = [9,15,7,20,3]

Возвращает следующее бинарное дерево:

图片.png

Код ссылки

Определение дерева

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int          // 根
 *     Left *TreeNode   //左节点
 *     Right *TreeNode  //右节点
 * }
 */

языковая версия ГОрекурсия

  1. Чтобы знать, что это дерево, оно выражается только в виде массива

图片.png

Просто используйте это дерево в качестве примера

ключевой момент :

Пост-порядковый обход для определения корневого узла

Определение прохождения подпоследовательности влево и правые узлыВ среднем обходе находим корневой узел, левый — левое поддерево, правый — правое дерево.

Затем рекурсивно продолжаем искать корень в левом поддереве и левое поддерево левого поддерева

То же верно и для правого поддерева.

func buildTree(inorder []int, postorder []int) *TreeNode {
    idxMap := map[int]int{}
    for i, v := range inorder {
        idxMap[v] = i
    }
    var build func(int, int) *TreeNode
    build = func(inorderLeft, inorderRight int) *TreeNode {
        // 无剩余节点
        if inorderLeft > inorderRight {
            return nil
        }

        // 后序遍历的末尾元素即为当前子树的根节点
        val := postorder[len(postorder)-1]
        postorder = postorder[:len(postorder)-1]
        root := &TreeNode{Val: val}

        // 根据 val 在中序遍历的位置，将中序遍历划分成左右两颗子树
        // 由于我们每次都从后序遍历的末尾取元素，所以要先遍历右子树再遍历左子树
        inorderRootIndex := idxMap[val]
        root.Right = build(inorderRootIndex+1, inorderRight)
        root.Left = build(inorderLeft, inorderRootIndex-1)
        return root
    }
    return build(0, len(inorder)-1)
}

Java-версия

 /**
     * 例如，给出
     *
     * 中序遍历 inorder = [9,3,15,20,7]
     * 后序遍历 postorder = [9,15,7,20,3]
     * 返回如下的二叉树：
     *
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     *    关键点:  1.两个数组的下标 0 和 len-1，先找后序的根，根据根来区分中序的左子树和右子树
     *            2.左节点递归(0~根-1，0~后序左+左子树-1）
     *            3.右节点递归（左子树+1~中序右边，后序左+左子树~后序右-1）
     *
     */
    private static int[] inorder = {15,9, 12, 3, 15, 20, 7 }; // 中序遍历 确定左右节点
    private static int[] postorder = { 15,12, 9, 15, 7, 20, 3 }; // 后序遍历 确定根节点
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode root = create(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
        return root;
    }
    private static TreeNode create(int[] inorder, int[] postorder, int inLeft, int inRight, int postLeft, int postRight) {
        if(postLeft > postRight){
            return null;   // 16. 退回到上一颗数15,null,null
        }
        TreeNode treeNode = new TreeNode(postorder[postRight]); // 1. 先找后序最后一个数，就是根节点   10.根节点为后序数组中的9 14.根是15
        int k = 0;
        for(int i = inLeft; i <= inRight; i++){ // 2.遍历一下中序数组
            if(inorder[i] == postorder[postRight]){ // 3.  如果数据里的值 = 根节点
                k = i;  // 4.根节点下标赋值给k = 3  11.根节点下标1   15. 0
                break;
            }
        }
        int numLeft = k - inLeft; // 5.（左子树的长度 = 3）在中序遍历中找到根节点，左边就是左子树，右边就是右子树  12. 1
        // 6. 左节点递归(0~根-1，0~后序左+左子树-1） 确定中序遍历的左子树的范围，0~2，  13. 0~1-1，0~0+1-1
        // 7.根据后序遍历特性：（左右根），根据第6步知道左子树的范围是0~2，所以在后序数组中的左子树范围也是0~2，并且知道下标2是根节点，值为9
        // 8.postLeft + numLeft - 1    19.回到9,null,null
        treeNode.left = create(inorder, postorder, inLeft, k - 1, postLeft, postLeft + numLeft - 1);
        // 17. 右节点递归（左子树+1~中序右边，后序左+左子树~后序右-1）此时左子树为15,null,null 它的左子树长度为0，所以要找左子树右节点：会return
        treeNode.right = create(inorder, postorder, k + 1, inRight, postLeft + numLeft, postRight - 1);  // 20 回到9,15,null 继续找左子树12这个根节点
        return treeNode; // 18.执行此步奏
    }

Искренне благодарю красивых и красивых девушек за то, что увидели это.Если эта статья будет хорошо написана, если вы почувствуете, что есть что-то

Ставьте лайк 👍 Подписывайтесь ❤️ Делитесь 👥 Мне очень полезно с 8 пакетами пресса! ! !

Если в этом блоге есть какие-либо ошибки, пожалуйста, критикуйте и посоветуйте, это очень ценится! ❤️❤️❤️❤️

Категории