Medium
刷面經澈蚌，這個題居然又不會做了，這個講解很不錯幫助到我理解.
https://www.youtube.com/watch?v=WqNULaUhPCc
分治法經典運用晌柬，注意到我們調用這個遞歸函數返回的情況只有兩種可能base case:
- 返回null,什么也沒找到
- 返回p或者q, 找到了
那么如果我們分別在左右子樹都返回了非空的TreeNode,說明我們兩邊都在base case return了一個非空的treenode, 即我們的p or q.說明兩個node分別在左右子樹共郭，這樣的話LCA就是root
如果我們有一邊返回了非空node,另一邊返回了空，說明我們在返回空的那一邊一無所獲什么也沒找到糠馆，那么我們就return left.為什么這里可以直接return left呢嘶伟，因為按照我們的函數，只要遇到能return的非空node,一定是先發(fā)現(xiàn)的那個又碌，也就是另一個p或者q肯定是它的子樹九昧，所有他倆的LCA肯定就是它了。
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null){
return null;
}
if (root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null){
return root;
}
if (left != null){
return left;
}
if (right != null){
return right;
}
return null;
}
}
