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

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

DFS+ 递归 + 前序中序特性

1. 由前序特性知道，第一个为根结点。由中序特性知道，根结点左边为左子树，右边为右子树。
2. 因此可以先在前序中确定根结点，然后在对应中序中找到根结点的位置，判断左子树的个数，然后回到前序来确定下一个根结点的位置，随后递归生成左右子树即可。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        return getTree(0, 0, n - 1, preorder, inorder);
    }
    public TreeNode getTree(int root, int start, int end, int[] preorder, int[] inorder) {
        if (start > end) {
            return null;
        }
        int i = start;
        //先在中序里面找到根结点的位置
        while (i < end && inorder[i] != preorder[root]) i ++;
        //求左子树的结点数量
        int lnode = i - start;
        TreeNode r = new TreeNode();
        r.val = preorder[root];
        //递归构建左右子树
        r.left = getTree(root + 1, start, i - 1, preorder, inorder);
        r.right = getTree(root + lnode + 1, i + 1, end, preorder, inorder);
        return r;
    }
}