236. Lowest Common Ancestor of a Binary Tree

Leetcode link

题目简介

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */

本题给我们一颗二叉树的根节点 root 以及两个树中的元素 p 与 q

题目要求我们找到并返回 p 与 q 的最小公共祖先节点 LCA

解题思路

要找 LCA，我们一般使用 DFS 来寻找

我们需要在找到 p 跟 q 的时候把这个信息 “向上传递”

第一个同时接收到 p 跟 q 信息的节点就是两者的 LCA

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    if(!root || root === p || root === q){
        return root
    }

    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)

    if(left && right) {
        return root
    }

    return left || right
};