题解 | #在二叉树中找到两个节点的最近公共祖先#
在二叉树中找到两个节点的最近公共祖先
https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116
package main
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
*
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
func lowestCommonAncestor(root *TreeNode, o1 int, o2 int) int {
sta1 := make([]int, 10)
sta2 := make([]int, 10)
sta1, top1 := find(root, o1, sta1, 0)
sta2, top2 := find(root, o2, sta2, 0)
a := sta1
b := sta2
for i, j := top1-1, top2-1; ; {
i--
j--
if i < 0 && j < 0 {
return -1
}
if i < 0 {
i = top2 - 1
a = sta2
}
if j < 0 {
j = top1 - 1
b = sta1
}
if a[i] == b[j] {
return a[i]
}
}
return -1
}
func find(root *TreeNode, o int, sta []int, top int) (st []int, t int) {
if root == nil {
return sta, -1
}
if len(sta) <= top {
sta = append(sta, root.Val)
} else {
sta[top] = root.Val
}
top++
if root.Val == o {
return sta, top
}
sta, left := find(root.Left, o, sta, top)
if left >= 0 {
return sta, left
}
return find(root.Right, o, sta, top)
}
虾皮信息公司福利 754人发布