题解 | #在二叉树中找到两个节点的最近公共祖先#

1. 如果root节点左右都能找到，说明这两个节点分别位于两个子树，返回root
2. 如果左子树没有，则返回右子树
3. 如果右子树没有，则返回左子树
4. 如果都没有，返回null

    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        return _lowestCommonAncestor(root, p, q).val;
    }
    public TreeNode _lowestCommonAncestor(TreeNode root, int p, int q) {
        if (root == null) {
            return null;
        }
        if (root.val == p || root.val == q) {
            return root;
        }
        TreeNode leftNode = _lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = _lowestCommonAncestor(root.right, p, q);
        if (leftNode == null) {
            return rightNode;
        }
        if (rightNode == null) {
            return leftNode;
        }
        return root;
    }