二叉搜索树的最近公共祖先
题目描述
示例
代码
代码1 递归,利用二叉搜索树的特性
js
/*
递归
*/
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 深度优先遍历 遍历两次 找到路径后 硬解
js
/*
深度优先遍历 分别找到到两个节点的路径
把路径保存到数组中
然后两个路径有长有短,只需要遍历短的长度即可,因为路径都是从根节点开始的,最差也会返回一个根节点
比如 一个路径为 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):两个存储路径的数组和递归的栈内存开销。