乐趣区

关于javascript:二叉树寻找最近公共祖先节点

办法一:递归

1. 思路

(1)定义 fx 示意 x 节点的子树中是否蕴含 p 或者 q 节点,如果蕴含为 true, 否则为 false。那么符合条件的最近公共先人节点肯定满足上面的条件:

(flson && frson) || ((x = p || x = q) && (flson || frson))

其中 flson 和 frson 别离示意左子树含有 p 或 q 节点。

(2)若想找到最近公共先人节点,必须应用深度遍历实现

2. 实现

var lowestCommonAncestor = function(root, p, q) {if(!root)   return null;            // 如果根节点为空的话,间接返回 null
    let result;            // 定义返回值
    const dfs = (root, p, q) => {
        // 先定义深度遍历递归的条件
        if(!root)   return false;
        let lson = dfs(root.left, p, q);        // 先从左子树开始深度遍历
        let rson = dfs(root.right, p, q);       // 再从右子树开始深度遍历
        if((lson && rson) || ((root === q || root === p) && (lson || rson))) {
            // 如果合乎该条件的话,就是找到了最近的公共先人节点
            result = root;
        }
        // 只有有一项符合要求的话,就返回 true
        return lson || rson || root === p || root === q;
    }
    dfs(root, p, q);
    return result;
};
退出移动版