【根据前序和中序遍历构造二叉树】栈+迭代 || 递归

105. 从前序与中序遍历序列构造二叉树

栈+迭代

规律

• 前序遍历中相邻节点u和v，v节点一定是u节点的左节点或者是其自身某个祖先的右节点
• 一个没有右节点的链，中序遍历是从叶子到根，前序遍历是从根到叶子

解题思路

1. 用一个栈维护前序遍历的节点
2. 用一个指针p指向中序遍历的第一个叶子节点
3. 遍历前序，一直遍历到p指向的叶子节点，都持续是其父节点的左儿子，入栈即可。
4. 若遍历到的节点的上一个节点为p指向的叶子节点，那么该节点就是树链（栈）上某个节点的右节点。如何找到其父亲？
5. 使指针p在中序遍历上右移，同时在树链（栈）上回溯（弹栈），找到最后一个相同的节点，则为其父亲。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = new TreeNode(preorder[0]);
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        int iIn = 0;
        TreeNode now = root;
        for(int i = 1; i < preorder.length; ++ i) {
            if(preorder[i - 1] != inorder[iIn]) {
                now.left = new TreeNode(preorder[i]);
                s.push(now.left);
                now = now.left;
            } else {
                while(!s.empty() && s.peek().val == inorder[iIn]) {
                    now = s.pop();
                    iIn ++ ;
                }
                now.right = new TreeNode(preorder[i]);
                s.push(now.right);
                now = now.right;
            }
        }
        return root;
    }
}

递归

• 根节点在先序遍历中左右子树区间长度和在中序遍历中区间长度一致

1. 先序遍历的子树区间第一个节点一定是根
2. 定位中序遍历中根的位置，根的左子树区间在其左边，右子树区间在其右边，由此得到左右子树区间长度
3. 由得到的左右子树区间长度来定位在先序遍历中的子树区间
4. 再构建两棵子树，层层递归即可

class Solution {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; ++ i ) {
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length-1, 0, preorder.length-1);
    }

    public TreeNode build(int[] preorder, int preL, int preR, int inL, int inR) { // [preL, preR] [inL, inR]
        int val = preorder[preL];
        TreeNode root = new TreeNode(val);
        if(preL == preR) return root;
        int inId = map.get(val);
        int numL = inId - inL; // 左子树大小
        int numR = inR - inId; // 右子树大小

        if(numL > 0) root.left = build(preorder, preL + 1, preL + numL, inId - numL, inId - 1);
        if(numR > 0) root.right = build(preorder, preL + numL + 1, preR, inId + 1, inId + numR);

        return root;
    }
}