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

题目描述

示例

代码

代码1 两次深度优先遍历，找到各自的路径，然后找最近公共父节点的值

/*
深度优先遍历 分别找到到两个节点的路径
把路径保存到数组中
然后两个路径有长有短，只需要遍历短的长度即可，因为路径都是从根节点开始的，最差也会返回一个根节点
比如 一个路径为 3 5 6
另一个路径为 3 5 2 7
一个节点是6，一个节点是7，所以只需比较三次即可
*/
function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    
    let arr1 = [] // 保存到达o1的路径
    let arr2 = [] // 保存到达o2的路径
    
    // 是否找到了这个节点，如果找到了就更新为true，跳出搜索
    let isFind = false 
    
    // dfs遍历root，分别找到到达o1和o2的路径信息
    dfs(root, o1, arr1)
    isFind = false // 重置一下
    dfs(root, o2, arr2)
    
    // 开始查找最近的公共父节点，从头开始找
    let i = 0
    let result = null // 找到的最近父节点
    let size = Math.min(arr1.length,arr2.length)
    
    while( i < size){ // 倒着找，从倒数第二个开始找
        if(arr1[i] !== arr2[i]) break;
        result = arr1[i]
        i++
    }
    
    return result // 返回最近公共父节点
    
    
    // 深度遍历，找到路径，保存到数组中
    function dfs(root, o, arr){
        // 出口，遍历到最后的空节点了
        if(root === null) return
        
        arr.push(root.val)
        // 如果找到了，更新标识，递归提前返回结果
        if(root.val === o) {
            isFind = true
            return
        }
        
        dfs(root.left, o, arr)
        if(isFind) return // 如果已经找到了，提前返回
        dfs(root.right, o, arr)
        if(isFind) return // 如果已经找到了，提前返回
        
        // 如果发生回溯了，路径减一（即：把最后一个塞进去的值pop出去）
        arr.pop()
    }
    
}

时间复杂度O(n)：两次dfs递归，每次最多递归n次。

空间复杂度O(n)：两个存储路径的数组和递归的栈内存开销。

代码2 递归求解（得仔细寻思代码才能想明白）

/*
递归求解
三种情况
1. 都在左侧
2. 都在右侧
3. 左右两侧
*/
function lowestCommonAncestor( root ,  o1 ,  o2 ) {
    
    return dfs(root ,  o1 ,  o2).val
    
    function dfs(root ,  o1 ,  o2) {
        if(root === null) return null //超过叶节点，返回空
        if(root.val === o1 || root.val === o2) return root //节点为其中一个
        
        let lval = dfs(root.left ,  o1 ,  o2)
        let rval = dfs(root.right ,  o1 ,  o2)
        if(lval === null) return rval //此时两个节点都在右侧 \
        if(rval === null) return lval //此时两个节点都在左侧 /
        
        return root //此时两个节点分别位于左右两侧 / \
    }
}

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

时间复杂度O(n)

空间复杂度O(n)

题目来源

JZ86 在二叉树中找到两个节点的最近公共祖先