二叉树的最近公共祖先

题解方法

• 深度优先搜索

深度优先搜索

边界条件

1. 当前节点为空，说明搜到底部，搜索结束。
2. 当前节点等于目标节点，说明搜到目标节点，返回当前节点。

搜索路径

1. 分别搜索当前节点的左右子树。
2. 如果某一子树为空，则说明目标节点均在另一棵子树上。
3. 否则目标节点分别在两子树上。

核心代码

深度优先搜索

public TreeNode searchCommonAncestor(TreeNode node, TreeNode p, TreeNode q) {
    if (null == node) {
        return null;
    }
    if (node == p || node == q) {
        return node;
    }

    TreeNode left = searchCommonAncestor(node.left, p, q);
    TreeNode right = searchCommonAncestor(node.right, p, q);

    if (null == left) {
        return right;
    }
    if (null == right) {
        return left;
    }

    return node;
}

题目来源

• 236. 二叉树的最近公共祖先 - 力扣（LeetCode）