forked from xiaoyaoworm/Leetcode-java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path106_inPost_buildTree.java
More file actions
29 lines (26 loc) · 1004 Bytes
/
Copy path106_inPost_buildTree.java
File metadata and controls
29 lines (26 loc) · 1004 Bytes
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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder,postorder,0, inorder.length-1,0,postorder.length-1);
}
public TreeNode build(int[] inorder, int[] postorder, int in_start, int in_end, int post_start, int post_end){
if(in_start > in_end || post_start > post_end) return null;
int rootVal = postorder[post_end];
TreeNode root = new TreeNode(rootVal);
int k = 0;
while(inorder[in_start+k]!=rootVal){ //be careful this index is not k, this is in_start+k
k++;
}
root.left = build(inorder,postorder,in_start,in_start+k-1,post_start,post_start+k-1);
root.right = build(inorder,postorder,in_start+k+1,in_end,post_start+k,post_end-1);
return root;
}
}