LeetCode： 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
三种情况
p、q 分别在节点的左子树、右子树p 、q 都在节点的左子树 （该节点的可能性包括自身 p | q）p、 q 都在节点的右子树 （该节点的可能性包括自身 p | q）当我们往下遍历 当同时找到两个 left 、right 都不为 null，表示当前就是最近父节点 当只找到其中一个，直接返回，因为它就是父节点，因为另一个必定在它的左或者右子树
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { return dfs(root, p, q); } public TreeNode dfs(TreeNode node, TreeNode p, TreeNode q){ if(node == null) return null; if(node.val == p.val || node.val == q.val) return node; TreeNode left = dfs(node.left, p, q); TreeNode right = dfs(node.right, p, q); if(left != null && right != null){ return node; } else if(left != null){ return left; } else { // right != null return right; } } }