236. Lowest Common Ancestor of a Binary Tree 【M】多体会
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
http://www.jiuzhang.com/solutions/lowest-common-ancestor/
Discussion Answer: Divide and Conquer – Best version -- Same as jiuzhang
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// if root.val == p.val, that is wrong answer.
if (root == null || root == p || root == q)
return root;
// Divide
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// Couquer
if (left == null)
return right;
else if (right == null)
return left;
return root;
}
}
*总结：
首先不能用binary search的性质，看左右控制判断了。
最后的判断以及前面的判断加起来的逻辑就是：
返回null的情况只有一种，那就是没有找到p / q等于根的时候。
一旦找到了就不会返回null，返回的就是root