235. Lowest Common Ancestor of a Binary Search Tree
上一题：找最小公共祖先，可以是自身。［二叉搜索树］
236. Lowest Common Ancestor of a Binary Tree
找最小公共祖先，可以是自身。［非二叉树］
递归的方式。我们可以这样来看，对于任意的一个节点来说，如果以它为根节点去找两个节点的最低公共父节点，首先需要的是找到它的左右子树中是否存在有要查找的两个节点中的一个。如果找到任意一个则返回，否则返回null。而在回溯的时候，对于这个最低公共子节点有一个特性，它必然左右子节点返回的值都不为空的，而其他节点则总会有一个为空。所以在回溯的时候，如果它们中间有一个非空则返回不空的那个，如果左右子树的节点都不空则返回当前节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || 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;
return left!=null ? left:right;
}
}
