剑指offer4J【C2 P7】重建二叉树

题目

根据树的前序、中序遍历构建出树结构

题解

什么是前序、中序我就不带大家复习了 根左右 左根右。

可爱的小树

前序遍历 [3,9,20,15,7]

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

---

• 根据前序遍历特点 我们能立刻得知，前序遍历的第一个元素，即是这棵树的根节点root节点，前序遍历中 我们可以粗略把数组内容分成3段：根、所有左元素、所有右元素（黄根、绿左、蓝右）。

前序分隔

• 前序遍历中，root节点的下一个节点即是第一个左孩子（即节点9），那第一个右孩子呢？
• 其实只要能够计算出左元素个数我们就能根据root节点计算出第一个右孩子在前序遍历中的相对位置 即 root节点下标+ 左元素个数 +1 即是第一个右孩子下标

中序分隔

• root节点下标是前序的第一个元素，那左元素个数我们怎么计算呢？我们不妨找到根节点在中序遍历中的下标 他的左侧即是全部左元素，他的右侧即是全部右元素。例如上图：我们根据中序可以发现root节点 3左侧有1个元素，那么在前序遍历中，从根节点数起，向后数2位，即是第一个右子树元素。
• 此时，我们已经能够构建、获取树的root、第一个左、第一个右，我们只要把第一个左、第一个右当作是新的root，进行上述逻辑的递归，即可构建出完整的树。
• 但是有一点需要注意，在根据中序计算左右元素数量的时候应当控制元素边界，每次以root将中序数组分割成3部分，全部左、root、全部右。

    private int [] preorder;
    private Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        map = new HashMap<>(inorder.length);
        for (int i=0;i<inorder.length;i++) map.put(inorder[i],i);
        return buildTree(0,0,preorder.length-1);
    }
    private TreeNode buildTree(int rootIndexForPre,int startIndexForIn,int endIndexForIn){
        if(startIndexForIn>endIndexForIn) return null;
        TreeNode root = new TreeNode(preorder[rootIndexForPre]);
        int rootIndexForIn = map.get(preorder[rootIndexForPre]);
        root.setLeft(buildTree(rootIndexForPre+1,startIndexForIn,rootIndexForIn-1));
        root.setRight(buildTree(rootIndexForIn-startIndexForIn+rootIndexForPre+1,rootIndexForIn+1,endIndexForIn));
        return root;
    }

---

源码: 剑指offer4J