二叉搜索树的最近公共祖先

题目描述

示例

代码

代码1 递归，利用二叉搜索树的特性

/*
递归
*/
function lowestCommonAncestor( root ,  p ,  q ) {
    // write code here
    let min = Math.min(p ,  q)
    let max = Math.max(p ,  q)
    
    return dfs(root ,  min ,  max).val
    
    function dfs(root ,  min ,  max) {
        if(root === null) return null // 没找到呢
        if(root.val === p || root.val === q) return root // 找到了
        
        /*
            // 不是二叉搜索树的递归 如下
            let lval = dfs(root.left ,  p ,  q)
            let rval = dfs(root.right ,  p ,  q)

            // 都在左侧时
            if(rval == null) return lval
            // 都在右侧时
            if(lval == null) return rval

            // 否则就是在左右两侧
            return root
        */
        
        // 因为是二叉搜索树了，可以利用他的特性，左子树小于 根 小于右子树
        if(root.val > max){ // 比两个值都大时，从左边找
            return dfs(root.left ,  min ,  max)
        }else if(root.val < min) {//比两个值都小时，从右边找
            return dfs(root.right ,  min ,  max)
        }else { // p q 的值介于中间，就是左右两侧
            return root
        }
    }
}

时间复杂度O(n)

空间复杂度O(n)

代码2 深度优先遍历 遍历两次 找到路径后 硬解

/*
深度优先遍历 分别找到到两个节点的路径
把路径保存到数组中
然后两个路径有长有短，只需要遍历短的长度即可，因为路径都是从根节点开始的，最差也会返回一个根节点
比如 一个路径为 3 5 6
另一个路径为 3 5 2 7
一个节点是6，一个节点是7，所以只需比较三次即可
*/
function lowestCommonAncestor( root ,  p ,  q ) {
    let arr1 = [] // 保存到达p的路径
    let arr2 = [] // 保存到达q的路径
    
    // 是否找到了这个节点，如果找到了就更新为true，跳出搜索
    let isFind = false 
    
    // dfs遍历root，分别找到到达o1和o2的路径信息
    dfs(root, p, arr1)
    isFind = false // 重置一下
    dfs(root, q, 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)：两个存储路径的数组和递归的栈内存开销。

题目来源

JZ68 二叉搜索树的最近公共祖先