先序遍历-258，从前序与中序遍历序列构造二叉树_橙果行动派·副业优质付费资源·知识付费网课平台

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:

你可以假设树中没有重复的元素。

例如，给出

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

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

返回如下的二叉树：

9 20

15 7

答案：

 1public TreeNode buildTree1(int[] preorder, int[] inorder) {
 2    return helper(0, 0, inorder.length - 1, preorder, inorder);
 3}
 4
 5public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
 6    if (preStart > preorder.length - 1 || inStart > inEnd) {
 7        return null;
 8    }
 9    TreeNode root = new TreeNode(preorder[preStart]);
10    int inIndex = 0; 
11    for (int i = inStart; i <= inEnd; i++) {
12        if (inorder[i] == root.val) {
13            inIndex = i;
14        }
15    }
16    root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
17    root.right = helper(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, preorder, inorder);
18    return root;
19}

解析：

关于二叉树的各种题先序遍历先序遍历，我们最常见的就是递归，这题的主要思想是我们已经知道前序遍历和中序遍历，前序遍历就意味着pre[0]是根节点，然后我们再找出他在中序遍历中的位置，在这个位置之前的是根节点的左节点，在这个位置之后的是根节点的右节点。然后再使用递归的方式遍历左右子树。这题不太好理解的是第17行的代码中的 + - + 1，其实也很好理解，我们可以认为是遍历到的当前节点的索引， - 当前节点的左子节点的个数，+ - + 1相当于当前节点的右子节点。这个看起来可能稍微有点不太好理解，下面再来换种写法，这种写法其实要更容易理解一些。

 1public TreeNode buildTree(int[] preorder, int[] inorder) {
 2    List preorderList = new ArrayList();
 3    List inorderList = new ArrayList();
 4    for (int i = 0; i < preorder.length; i++) {
 5        preorderList.add(preorder[i]);
 6        inorderList.add(inorder[i]);
 7    }
 8    return helper(preorderList, inorderList);
 9}
10
11private TreeNode helper(List preorderList, List inorderList) {
12    if (inorderList.size() == 0)
13        return null;
14    int ind = inorderList.indexOf(preorderList.remove(0));
15    TreeNode root = new TreeNode(inorderList.get(ind));
16    root.left = helper(preorderList, inorderList.subList(0, ind));
17    root.right = helper(preorderList, inorderList.subList(ind + 1, inorderList.size()));
18    return root;
19}

这种解法不断的用前序遍历的值把中序遍历的集合分为两部分，前面部分成为左子节点的集合，后面部分成为右子节点的集合。下面来看个不是递归的写法

 1public TreeNode buildTree(int[] preorder, int[] inorder) {
 2    if (preorder.length == 0) 
 3        return null;
 4    Stack s = new Stack();
 5    TreeNode root = new TreeNode(preorder[0]), cur = root;
 6    for (int i = 1, j = 0; i < preorder.length; i++) {
 7        if (cur.val != inorder[j]) {
 8            cur.left = new TreeNode(preorder[i]);
 9            s.push(cur);
10            cur = cur.left;
11        } else {
12            j++;
13            while (!s.empty() && s.peek().val == inorder[j]) {
14                cur = s.pop();
15                j++;
16            }
17            cur = cur.right = new TreeNode(preorder[i]);
18        }
19    }
20    return root;
21}