LeetCode - Algorithms - 105. Construct Binary Tree from Preorder and Inorder Traversal

二叉树自己能理解一二，不算难。自己也观察出来了从Preorder里知道根结点，再在Inorder里划分左右子树，如此不断递归二分。代码抄袭了这个的：
LeetCode – Construct Binary Tree from Preorder and Inorder Traversal (Java)

From the pre-order array, we know that first element is the root. We can find the root in in-order array. Then we can identify the left and right sub-trees of the root from in-order array. Using the length of left sub-tree, we can identify left and right sub-trees in pre-order array. Recursively, we can build up the tree.

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    	int preStart=0;
    	int preEnd=preorder.length-1;
    	int inStart = 0;
    	int inEnd = inorder.length-1;
        return buildTree(preorder,preStart,preEnd,inorder,inStart,inEnd);
    }

    public TreeNode buildTree(int[] preorder, int preStart,int preEnd, int[] inorder, int inStart, int inEnd) {
    	if (preStart>preEnd || inStart>inEnd)
    	  return null;

    	int val = preorder[preStart];
    	TreeNode rt = new TreeNode(val);

    	int k=0;
    	for(int i=0;i<=inEnd;i++) {
    		if (inorder[i]==val) {
    			k=i;
    			break;
    		}
    	}

    	rt.left = buildTree(preorder, preStart+1, preStart+(k-inStart),inorder,inStart,k-1);
    	rt.right = buildTree(preorder, preStart+(k-inStart)+1, preEnd, inorder, k+1, inEnd);

    	return rt;
    }    
}

Submission Detail

  • 203 / 203 test cases passed.
  • Runtime: 13 ms
  • Your runtime beats 55.29 % of java submissions.