从中序与后序遍历序列构造二叉树-一一网

【Golang主题学习月】刷题比玩游戏好多了，成就感越来越强，每天坚持刷一道题，每天锻炼30分钟，等8块腹肌,等大厂offer.

$\color{red}{~}$

假期每日一题~~~

leecode 106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

图片.png

参考代码

定义一颗树

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

GO语言版 递归

要知道这是一棵树，只是通过数组的形式表现出来的

图片.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.执行此步奏
    }



复制代码