105. 从前序与中序遍历序列构造二叉树（中等 二叉树 dfs 哈希表 二叉树）

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

本题需要理解二叉树前序遍历和中序遍历的过程，以及两者的关系。
方法一：哈希表 + 递归
前序遍历的节点顺序是：根->左子树的前序遍历->右子树的前序遍历；
中序遍历的节点顺序是：左子树的中序遍历->根->右子树的中序遍历；
通过定位到中序遍历中的根节点，就可以知道左子树和右子树的节点数目，结合前序遍历中的根节点位置就可以得知根节点的左右子树的前序和中序遍历结果，通过递归构造出左右子树再连接即可。
要找到根节点可以通过哈希表记录前序遍历中的节点和索引位置，这样就可以在中序遍历中快速找到对应根节点。
方法二：迭代
依据前序遍历和中序遍历的特点，对于前序遍历的连续的两个节点 u 和 v，有两种情况，v 是 u 的左子节点或者 v 是其某个父节点（不一定是 u）的右子节点，结合中序遍历我们可以判断第二种情况什么时候出现，其余情况下 v 都是 u 的左子节点。
我们遍历前序遍历的数组，同时用一个指针遍历中序遍历的数组，在遍历前序数组过程中把节点存储到栈里面，同时判断节点是否与指针指到的中序遍历数组中的节点相同，不同的话当前节点则是前一个节点的左子节点，否则向右移动指针并且弹出栈顶的节点，直到栈空或者栈顶节点与指针指向的节点相同，此时指针指向的节点即为最后pop出的节点的右子节点，一直遍历直到结束栈底元素即为需要构造的树。

题解（Java）

方法一：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        for (int i = 0; i < n; i++) {
            map.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }

		// 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = map.get(preorder[preorder_root]);

		// 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 获得左子树节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 构造左子树并连接根节点
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 构造右子树并连接根节点
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

方法二：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42