Skip to content

Commit 087c1e4

Browse files
clean up and add more notes
1 parent 56d3041 commit 087c1e4

File tree

2 files changed

+37
-9
lines changed

2 files changed

+37
-9
lines changed

src/main/java/com/stevesun/solutions/_105.java

Lines changed: 13 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -11,24 +11,34 @@
1111
You may assume that duplicates do not exist in the tree.*/
1212
public class _105 {
1313

14-
//credit: https://discuss.leetcode.com/topic/29838/5ms-java-clean-solution-with-caching
15-
//use HashMap as the cache so that accessing inorder index becomes O(1) time
14+
/**credit: https://discuss.leetcode.com/topic/29838/5ms-java-clean-solution-with-caching
15+
use HashMap as the cache so that accessing inorder index becomes O(1) time
16+
17+
Note: The first element of preorder array is the root!*/
1618
public TreeNode buildTree(int[] preorder, int[] inorder) {
1719
Map<Integer, Integer> inorderMap = new HashMap();
1820
for (int i = 0; i < inorder.length; i++) {
1921
inorderMap.put(inorder[i], i);
2022
}
2123

24+
/**At the beginning, both start from 0 to nums.length-1*/
2225
return buildTree(preorder, 0, preorder.length-1, 0, inorder.length-1, inorderMap);
2326
}
2427

2528
private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int inStart, int inEnd, Map<Integer, Integer> inorderMap) {
2629
if (preStart > preEnd || inStart > inEnd) return null;
2730

2831
TreeNode root = new TreeNode(preorder[preStart]);
29-
int inRoot = inorderMap.get(root.val);
32+
int inRoot = inorderMap.get(preorder[preStart]);
3033
int numsLeft = inRoot - inStart;
3134

35+
/**It's easy to understand and remember:
36+
* for the indices of inorder array:
37+
* root.left should be inStart and inRoot-1 as new start and end indices
38+
* root.right should be inRoot+1 and inEnd as new start and end indices
39+
*
40+
* since inRoot is being used already in this recursion call, that's why we use inRoot-1 and inRoot+1
41+
* this part is the same for both Leetcode 105 and Leetcode 106.*/
3242
root.left = buildTree(preorder, preStart+1, preStart+numsLeft, inStart, inRoot-1, inorderMap);
3343
root.right = buildTree(preorder, preStart+numsLeft+1, preEnd, inRoot+1, inEnd, inorderMap);
3444
return root;

src/main/java/com/stevesun/solutions/_106.java

Lines changed: 24 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -16,8 +16,11 @@
1616
*/
1717
public class _106 {
1818

19-
//credit: https://discuss.leetcode.com/topic/3296/my-recursive-java-code-with-o-n-time-and-o-n-space
20-
/**The idea is to take the last element in postorder as the root; find the position of the root in the inorder array;
19+
/**https://discuss.leetcode.com/topic/3296/my-recursive-java-code-with-o-n-time-and-o-n-space
20+
*
21+
* Note: the last element of postorder array is the root!
22+
*
23+
* The idea is to take the last element in postorder as the root; find the position of the root in the inorder array;
2124
* then locate the range for left sub-tree and right sub-tree and do recursion,
2225
* use a hashmap to record the index of root in the inorder array.*/
2326
public TreeNode buildTree(int[] inorder, int[] postorder) {
@@ -28,17 +31,32 @@ public TreeNode buildTree(int[] inorder, int[] postorder) {
2831
for (int i = 0; i < inorder.length; i++) {
2932
inorderMap.put(inorder[i], i);
3033
}
34+
/**At the beginning, both start from 0 to nums.length-1*/
3135
return buildTreeRecursively(0, inorder.length-1, postorder, 0, postorder.length-1,inorderMap);
3236
}
3337

3438
private TreeNode buildTreeRecursively(int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd, Map<Integer, Integer> inorderMap){
3539
if (postorderStart > postorderEnd || inorderStart > inorderEnd) return null;
3640
TreeNode root = new TreeNode(postorder[postorderEnd]);
3741
int inRoot = inorderMap.get(postorder[postorderEnd]);
38-
TreeNode leftchild = buildTreeRecursively(inorderStart, inRoot-1, postorder, postorderStart, postorderStart+inRoot-inorderStart-1, inorderMap);
39-
TreeNode rightchild = buildTreeRecursively(inRoot+1, inorderEnd, postorder, postorderStart+inRoot-inorderStart, postorderEnd-1, inorderMap);
40-
root.left = leftchild;
41-
root.right = rightchild;
42+
int numsLeft = inRoot-inorderStart;
43+
44+
/**It's easy to understand and remember:
45+
* for the indices of inorder array:
46+
* inStart and inRoot-1 as new start and end indices
47+
* inRoot+1 and inEnd as new start and end indices
48+
*
49+
* this is easy to understand and remember: since inRoot is already been used in this recursion call, so we're going to use inRoot-1 and inRoot+1 for next recursion call
50+
*
51+
* for the indices of postorder array:
52+
* postorderStart and postorderStart+numsLeft-1 should be the new start and end indices
53+
* postorderStart+numsLeft and postorderEnd-1 should be the new start and end indices
54+
*
55+
* this is also easy to understand and remember:
56+
* since the last one in postorder is the root and we have used it in this recursion call already, so the end is definitely postorderEnd-1;
57+
* then the postorderEnd for root.left is contiguous to the postorderStart of root.right, :)*/
58+
root.left = buildTreeRecursively(inorderStart, inRoot-1, postorder, postorderStart, postorderStart+numsLeft-1, inorderMap);
59+
root.right = buildTreeRecursively(inRoot+1, inorderEnd, postorder, postorderStart+numsLeft, postorderEnd-1, inorderMap);
4260
return root;
4361
}
4462

0 commit comments

Comments
 (0)