题目描述

算法

(DFS) $O(n)$

前序遍历的第一个元素肯定是根节点，那么前序遍历的第一个节点在中序位置之前的都是根节点的左子树，之后都是根节点的右子树。

Java 代码

class Solution {
    private int in = 0;
    private int pre = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MIN_VALUE);
    }

    private TreeNode build(int[] preorder, int[] inorder, int stop) {
        if (pre >= preorder.length) return null;

        if (inorder[in] == stop) {
            in++;
            return null;
        } 

        TreeNode node = new TreeNode(preorder[pre++]);
        node.left = build(preorder, inorder, node.val);
        node.right = build(preorder, inorder, stop);
        return node;
    }
}