LeetCode - Algorithms - 106. Construct Binary Tree from Inorder and Postorder Traversal

这题跟105. Construct Binary Tree from Preorder and Inorder Traversal是一个系列，代码抄袭了Construct Binary Tree from Inorder and Postorder Traversal，二叉树的算法应该说不难理解。

From the post-order array, we know that last 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 post-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[] inorder, int[] postorder) {
    	int inStart=0;
    	int inEnd=inorder.length-1;
    	int postStart=0;
    	int postEnd=postorder.length-1;
        return buildTree(inorder,inStart,inEnd,postorder,postStart,postEnd);
    }

    public TreeNode buildTree(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
    	if (inStart>inEnd || postStart>postEnd)
    		return null;

    	int rtVal = postorder[postEnd];
    	TreeNode rt = new TreeNode(rtVal);

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

    	rt.left = buildTree(inorder,inStart,k-1,postorder, postStart, postStart+k-inStart-1);
    	rt.right = buildTree(inorder,k+1,inEnd,postorder,postStart+k-inStart,postEnd-1);

    	return rt;
    }    
}

Submission Detail

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