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:
這道題目就比較簡(jiǎn)單了。他和上面那道題的區(qū)別是什么鲜侥。
如果p或者q == root褂始，那么，他們的祖先一定是root描函。因?yàn)闆](méi)找到的那個(gè)崎苗，一定在他的左右子樹(shù)上。而在上道題目中并不一定舀寓。
相當(dāng)于兩個(gè)點(diǎn)pq同時(shí)進(jìn)入這棵樹(shù)胆数。如果發(fā)現(xiàn)root的值正好大于等于其中一個(gè)然后小于等于另外一個(gè)，那么互墓，他就一定是最小祖先必尼。
否則，pq只能同時(shí)小于或者大于root.val篡撵，那么判莉，再選擇下一步遍歷的方向豆挽。
很類(lèi)似于pre-order,先判斷root結(jié)點(diǎn)
**
總結(jié)： 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;
}
}
我的做法代碼比較復(fù)雜。
然后看了 Discuss,發(fā)現(xiàn)有更加簡(jiǎn)潔的做法券盅。
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;
}
}
空間復(fù)雜度是 O(1)
現(xiàn)在的狀態(tài)出奇的差。跟女朋友關(guān)系飄忽不定渗饮。
突然發(fā)現(xiàn)她，才是我力量的源泉宿刮。沒(méi)有了她互站，我完全沒(méi)有斗志了。
其實(shí)現(xiàn)在準(zhǔn)備的也差不多了僵缺，過(guò)去真的就是各安天命胡桃。
整個(gè)浪費(fèi)的時(shí)間并不多，也不可能因?yàn)槔速M(fèi)這點(diǎn)時(shí)間而改變結(jié)果磕潮。
把面經(jīng)好好鞏固下翠胰，加油吧！
Anyway, Good luck, Richardo! -- 10/23/2016
