Paste_Image.png
My code:
/**
* 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 lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return null;
return findAncestor(root, p, q);
}
private TreeNode findAncestor(TreeNode root, TreeNode p, TreeNode q) {
if ((root.val >= p.val && root.val <= q.val) || (root.val <= p.val && root.val >= q.val))
return root;
if (root.val < p.val && root.val < q.val)
return findAncestor(root.right, p, q);
else if (root.val > p.val && root.val > q.val)
return findAncestor(root.left, p, q);
return null;
}
}
My test result:
Paste_Image.png
这道题目就比较简单了。他和上面那道题的区别是什么。
如果p或者q == root，那么，他们的祖先一定是root。因为没找到的那个，一定在他的左右子树上。而在上道题目中并不一定。
相当于两个点pq同时进入这棵树。如果发现root的值正好大于等于其中一个然后小于等于另外一个，那么，他就一定是最小祖先。
否则，pq只能同时小于或者大于root.val，那么，再选择下一步遍历的方向。
很类似于pre-order,先判断root结点
**
总结： pre-order tree
**
Anyway, Good luck, Richardo!
My code:
/**
* 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 lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) {
return null;
}
else if (p == q) {
return p;
}
TreeNode curr = root;
HashSet<TreeNode> tracker = new HashSet<TreeNode>();
while (curr != null) {
if (curr.val < p.val) {
tracker.add(curr);
curr = curr.right;
}
else if (curr.val > p.val) {
tracker.add(curr);
curr = curr.left;
}
else {
tracker.add(curr);
break;
}
}
curr = root;
TreeNode pre = null;
while (curr != null) {
if (!tracker.contains(curr)) {
return pre;
}
else if (curr.val < q.val) {
pre = curr;
curr = curr.right;
}
else if (curr.val > q.val) {
pre = curr;
curr = curr.left;
}
else {
return q;
}
}
return null;
}
}
我的做法代码比较复杂。
然后看了 Discuss,发现有更加简洁的做法。
both iteration and recursion
具体看
reference:
https://discuss.leetcode.com/topic/18381/my-java-solution
Anyway, Good luck, Richardo！ -- 08/28/2016
/**
* 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 lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode curr = root;
while (curr != null) {
if (p.val <= curr.val && curr.val <= q.val) {
return curr;
}
else if (q.val <= curr.val && curr.val <= p.val) {
return curr;
}
else if (p.val < curr.val && q.val < curr.val) {
curr = curr.left;
}
else {
curr = curr.right;
}
}
return null;
}
}
空间复杂度是 O(1)
现在的状态出奇的差。跟女朋友关系飘忽不定。
突然发现她，才是我力量的源泉。没有了她，我完全没有斗志了。
其实现在准备的也差不多了，过去真的就是各安天命。
整个浪费的时间并不多，也不可能因为浪费这点时间而改变结果。
把面经好好巩固下，加油吧！
Anyway, Good luck, Richardo! -- 10/23/2016
