二叉树的最近公共父节点

leetcode 235
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

leetcode 236
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

这两个题二字之差，一个是二叉搜索树，另一个是二叉树，搜索树是有序的，二叉树是无序的。

二叉搜索树还是比较好写的，我当时很快就写出来了。思路就是根据root与p和q的大小比较，递归的选择一边，直到root介于p和q之间。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }

        // 因为是有序的，所以只需要查找一边
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }

        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }

        return root;
    }
}

但是轮到二叉树就没写对， 我清楚二叉树相比搜索树是无序的，因此需要遍历两个分支，但是依然没写对 ，它的正确代码如下。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }

        // p或q在另一个的子树上
        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;
        }

        return left == null ? right : left;
    }
}

可以看到两个代码结构基本上是等效的，都对root是否为空判断，一个只需要查一边，一个需要查两边，root如果在p和q之间都返回root，但是后者base条件多了一种对如下情况的判断，我当时没有写。

if (root == p || root == q) {
    return root;
}

为啥额外增加这样一种判断呢？或者说搜索树为啥不用专门做这种判断？

对于二叉树来说这个判断避免一旦p和q其中之一为父节点继续往下递归，因为再往下寻找肯定返回null。而对于搜索树，因为有序，只有父节点同时严格小于或大于p和q才会往下递归，二叉树因为无序所以没有这种条件限制它，因此需要单独加上这个条件。

本以为这样就结束了，这时突然一个问题出现在我的脑海，那就是为啥root在p和q之间时就是最近的公共父节点？换句话说，当root在p和q之间时，继续往下找有没有可能出现更近的公共父节点？各位可能觉得这是一个明摆着的事情，可是当时我把自己问住了，好多事情就怕多问一个为什么🙃。是啊，感觉不太可能，可是为什么不可能呢？

对付这种杠精问题，最拿手的应该就是反证法了。我们假设root在p和q之间，p在左，q在右，在root的左子树上有一个更近的节点root'，那它必定不是q的父节点，如果root'在右子树，那它必定不是p的父节点，因此root的子树上不可能出现更近的公共父节点了。