Skip to content

Commit dc36b76

Browse files
awangdevawangdev
committed
day3
1 parent 79a5d42 commit dc36b76

13 files changed

Lines changed: 414 additions & 116 deletions

‎Java/Balanced Binary Tree.java‎

Lines changed: 66 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,12 @@
1+
1. DFS using depth marker: 每个depth都存一下。然后如果有不符合条件的，存为-1.
2+
一旦有-1， 就全部返回。
3+
最后比较返回结果是不是-1. 是-1，那就false
4+
5+
2. 从基本的题目理解考虑，想到leaf node的情况。如果判断了leaf node, 那其他node应该就是可以recursive。
6+
直接在isBalanced上面recursive.
7+
然后这个可能是个小小的优化，因为不需要计算所有的depth.一旦发现一个false,其他的就不需要计算，直接返回了。
8+
9+
```
110
/*
211
46% Accepted
312
Given a binary tree, determine if it is height-balanced.
@@ -17,12 +26,6 @@
1726
Tags Expand
1827
Tree Depth First Search
1928
20-
Thinking process:
21-
making use depth first search.
22-
same process as maxDepth() method.
23-
after recursive call, check if Math.abs(left - right) > 1. If so, return -1.
24-
If any case return -1, they all return -1.
25-
at the top return, check if -1.
2629
*/
2730

2831
/**
@@ -36,6 +39,61 @@ same process as maxDepth() method.
3639
* }
3740
* }
3841
*/
42+
43+
44+
/*
45+
12.11.2015
46+
Recap:
47+
The original way of marking depth and -1 is good. However, that has to traverse entire tree.
48+
49+
Today, let's think about the leaf case, and see if we can directly recurse on isBalanced itself.
50+
leaf case:
51+
root == null, return true;
52+
left = root.left; right = root.right;
53+
left == null && right == null : true;
54+
55+
left == null && right != null && (right.left != null || right.right != null) {
56+
false;
57+
}
58+
59+
need to isBalance(left) && isBalance(right).
60+
*/
61+
62+
public class Solution {
63+
/**
64+
* @param root: The root of binary tree.
65+
* @return: True if this Binary tree is Balanced, or false.
66+
*/
67+
public boolean isBalanced(TreeNode root) {
68+
if (root == null || (root.left == null && root.right == null)) {
69+
return true;
70+
}
71+
72+
TreeNode left = root.left;
73+
TreeNode right = root.right;
74+
//One of left or right is null.
75+
if (left == null && (right.left != null || right.right != null)) {
76+
return false;
77+
}
78+
if (right == null && (left.left != null || left.right != null)) {
79+
return false;
80+
}
81+
//none of left or right is null
82+
return isBalanced(left) && isBalanced(right);
83+
}
84+
}
85+
86+
87+
/*
88+
89+
Thinking process:
90+
making use depth first search.
91+
same process as maxDepth() method.
92+
after recursive call, check if Math.abs(left - right) > 1. If so, return -1.
93+
If any case return -1, they all return -1.
94+
at the top return, check if -1.
95+
96+
*/
3997
public class Solution {
4098
/**
4199
* @param root: The root of binary tree.
@@ -62,3 +120,5 @@ public int maxDepth(TreeNode root) {
62120
}
63121

64122

123+
124+
```

‎Java/Binary Tree Maximum Path Sum II.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,8 @@
2323
*/
2424

2525
/*
26-
Thoughts: maximum path sum from root, so it must include root, and it will be a single path from root to some point in the tree.
26+
Thoughts: maximum path sum from root, so it must include root, and it will be a single path
27+
from root to some point in the tree.
2728
(seems easier than Binary Tree Maximum path Sum I)
2829
'contains at least 1 node' -> at least have root.
2930
However, depending on child is positive or negative, we choose add or no add child

‎Java/Binary Tree Maximum Path Sum.java‎

Lines changed: 19 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,19 @@
66
情况1和情况2去一个最大值，
77
然后和情况三比较。
88
做了两个Math.max(). 然后就有了这一层的comboMax
9+
10+
11+
12.11.2015 recap:
12+
So totally, 5 conditions:
13+
(save in single:)
14+
left + curr.val
15+
right + curr.val
16+
(save in combo:)
17+
left,
18+
right,
19+
left + curr.val + right
20+
21+
922
```
1023
/*
1124
23% Accepted
@@ -40,8 +53,9 @@
4053
Thoughts:
4154
Don't assume positive integers .
4255
43-
Two steps of picking nodes: 1. Single Path (left or right)has a maximum. 2. Combine them into a final result: combinedPathMax
44-
1. singlePathMax, 2 results: either pick left+root or right+root.
56+
Two ways of picking nodes: 1. Single Path (left or right)has a maximum. 2. Combine them into a final result: combinedPathMax
57+
58+
1. singlePathMax, two results: either pick left+root or right+root.
4559
2. combinedPathMax: take left-max as a whole, take right-max as a whole.
4660
3 possible results: left-max without parent(like...when parent<0), right-max without parent(like...when parent<0), left-max + right-max + parent.
4761
3. Use a special container to store current node's singlePathMax and combinedPathMax.
@@ -81,6 +95,7 @@ public PathSumType helper(TreeNode root) {
8195
int singlePathMax = Math.max(left.singlePathMax, right.singlePathMax) + root.val;
8296
singlePathMax = Math.max(singlePathMax, 0);//If less than 0, no need to keep, because it only decrease parent-level max.
8397

98+
//first comparison: does not include curr node at all(this would be applicable when curr.val < 0, so we take this condition into account)
8499
int combinedPathMax = Math.max(left.combinedPathMax, right.combinedPathMax);
85100
combinedPathMax = Math.max(combinedPathMax, left.singlePathMax + right.singlePathMax + root.val);
86101

@@ -89,4 +104,6 @@ public PathSumType helper(TreeNode root) {
89104

90105
}
91106

107+
108+
92109
```

‎Java/Lowest Common Ancestor II.java‎

Lines changed: 62 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,18 @@
1-
找到的都存hashset. exist就return那个duplicate
1+
1. 曾经做的hashset的优化，找到的都存hashset. exist就return那个duplicate
2+
3+
4+
2. 正常做法：2 lists
25
```
36
/*
47
Lowest Common Ancestor II
58
6-
Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.
9+
Given the root and two nodes in a Binary Tree.
10+
Find the lowest common ancestor(LCA) of the two nodes.
711
812
The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.
913
10-
The node has an extra attribute parent which point to the father of itself. The root's parent is null.
14+
The node has an extra attribute parent which point to the father of itself.
15+
The root's parent is null.
1116
1217
Example
1318
For the following binary tree:
@@ -27,6 +32,60 @@ Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(L
2732
LintCode Copyright Binary Tree
2833
*/
2934

35+
/*
36+
Thoughts:
37+
我之前的做法也是蛮彪悍的，HashSet只存所需要的parent, 其实算是一个优化，更节省空间。
38+
12.11.2015.
39+
今天这个再来实现一个普通的做法，存在两个list里面。有parent的题目本身比没parent更简单。
40+
从头遍历两个list.
41+
1. 一旦分叉，分叉口的parent就是要找的。
42+
2. 如果两个list一直相等，那他们就是同一个node
43+
44+
border case: if both null, just return null.
45+
if only 1 is null, let one of the node be ancestor; since null can be anywhere.
46+
*/
47+
48+
public class Solution {
49+
/**
50+
* @param root: The root of the tree
51+
* @param A, B: Two node in the tree
52+
* @return: The lowest common ancestor of A and B
53+
*/
54+
public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
55+
ParentTreeNode A,ParentTreeNode B) {
56+
if (root == null || (A == null && B == null)) {
57+
return null;
58+
} else if (A == null || B == null) {
59+
return A == null ? B : A;
60+
}
61+
//Populate listA, listB
62+
ArrayList<ParentTreeNode> listA = new ArrayList<ParentTreeNode>();
63+
ArrayList<ParentTreeNode> listB = new ArrayList<ParentTreeNode>();
64+
65+
while (A != root) {
66+
listA.add(0, A);
67+
A = A.parent;
68+
}
69+
listA.add(0, A);
70+
while (B != root) {
71+
listB.add(0, B);
72+
B = B.parent;
73+
}
74+
listB.add(0, B);
75+
76+
int size = listA.size() > listB.size() ? listB.size() : listA.size();
77+
78+
for (int i = 0; i < size; i++) {
79+
if (listA.get(i) != listB.get(i)) {
80+
return listA.get(i).parent;
81+
}
82+
}
83+
84+
return listA.get(size - 1);
85+
}
86+
}
87+
88+
3089
/*
3190
Thoughts:
3291
Try to get upper-level parent, store in hashMap.

‎Java/Lowest Common Ancestor.java‎

Lines changed: 67 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -25,16 +25,79 @@ Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(L
2525
Binary Tree LintCode Copyright
2626
2727
28+
*/
29+
30+
/*
31+
Thoughts:
32+
Revisit this on 12.11.2015.
33+
To correctly understand this approach when there is not 'parent' atribute available in node.
34+
35+
We divide and coquer (in this case DFS) into 2 branches, and we are actually asking each node to check:
36+
Do I have a leaf child of nodeA (could be futher down in the tree)?
37+
Do I have a leaf child of nodeB (could be futher down in the tree)?
38+
1. If I have leaf child of A && B, then i'm the deepest parent! Return.
39+
2. If I only have A, or B: mark myself as an ancestor of A or B.
40+
3. If I don't have leaf child of A nor B, I'm not an ancestor, failed, return null.
41+
42+
After the common ancestor is found at any deep level, and returned itself to parent level,
43+
we can assume other branches must be null (because they are not ancestor, since we are),
44+
then the this common ancestor node will be passed to highest level.
45+
46+
However, with one problem:
47+
When review the problem, calling the recursive functions of the 'lowestCommonAncestor' is just
48+
confusing. It's not easy to see the relationship between leef child and ancestor candidates.
49+
50+
51+
*/
52+
public class Solution {
53+
/**
54+
* @param root: The root of the binary search tree.
55+
* @param A and B: two nodes in a Binary.
56+
* @return: Return the least common ancestor(LCA) of the two nodes.
57+
*/
58+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
59+
if (root == null || root == A || root == B) {
60+
return root;
61+
}
62+
TreeNode left = lowestCommonAncestor(root.left, A, B);
63+
TreeNode right = lowestCommonAncestor(root.right, A, B);
64+
65+
if (left != null && right != null) {//Found both A leaf and B leaf
66+
return root;
67+
} else if (left != null || right != null) {
68+
return left != null ? left : right;
69+
} else {
70+
return null;
71+
}
72+
}
73+
}
74+
75+
/*
76+
//Another way using regular way: see solution:
77+
This is for the case that each node can reach its higher level parent....
78+
Basically put all parents into a list,
79+
[root, next level, next level... parent, nodeA]
80+
[root, next level, next level... parent, nodeB]
81+
compare these 2 lists see when to have a different node. that node.parent is the parent
82+
83+
Or, if the list is identical, then their parent might just be same right-above-level parent.
84+
85+
http://www.ninechapter.com/solutions/lowest-common-ancestor/
86+
*/
87+
88+
89+
/*
90+
Older same version
2891
Think process:
2992
Divide and conquer:
3093
start from root, divide into 2 ways …
3194
At the bottom, if it’s node1 or node2, send back.
32-
If any line that’s not having node1 or node2 as leaf, they will become null.
33-
At the ancestor spot: because node1!=null and node2!=null, the ancestor return itself.
34-
From this point, any level higher, it will return the ancestor because the other child-line has been null at the time.
95+
1. If any line that’s not having node1 or node2 as leaf, they will become null.
96+
2. At the ancestor spot: because node1!=null and node2!=null, the ancestor return itself.
97+
3. From this point, any level higher, it will return the ancestor because the other child-line has been null at the time.
3598
When it returns to the top, return solution : ancestor
36-
*/
3799
100+
*/
38101
/**
39102
* Definition of TreeNode:
40103
* public class TreeNode {
@@ -70,7 +133,3 @@ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
70133
}
71134
}
72135
}
73-
/*
74-
//Another way using regular way: see solution:
75-
http://www.ninechapter.com/solutions/lowest-common-ancestor/
76-
*/

‎Java/Partition Array.java‎

Lines changed: 2 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
11
Partition Array根据pivot把array分成两半。
2-
从array两边开始缩进。while loop到便利完。非常直白的implement。
2+
从array两边开始缩进。while loop到遍历完。非常直白的implement。
33
注意low/high,或者叫start/end不要越边界
44
O(n)
55

6-
Merge sort的基础。
6+
Quick sort的基础。
77
```
88
/*
99
Given an array nums of integers and an int k, partition the array (i.e move the elements in "nums") such that:
@@ -71,14 +71,4 @@ public int helper(int[] nums, int start, int end, int pivot) {
7171
}
7272
}
7373

74-
75-
76-
77-
78-
79-
80-
81-
82-
83-
8474
```

‎Java/Partition List.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
不能想partitioin array一样从两边遍历。
1+
不能像partitioin array一样从两边遍历。
22

33
那就最普通的，建造两个list
44

0 commit comments

Comments
 (0)