思路
分享一个比较搞的思路。就是一个中序遍历可以扫出来所有节点的左右子树的节点数量,以及该节点在中序遍历中的下标。有了这部分信息,再次从根开始遍历二叉树,如果给定的两个节点下标均在当前遍历节点的左右子树的范围内,则很直观的就可以得出当前节点可以是这两个节点的LCA。遍历直至左右节点均无法满足LCA的条件。
时间复杂度是 $O(n)$的,由于要存所有节点的信息所以空间复杂度也是 $O(n)$。
Golang 代码
/**
* Definition for TreeNode.
* type TreeNode struct {
* Val int
* Left *ListNode
* Right *ListNode
* }
*/
type node struct {
index int
lcnt int
rcnt int
}
func inorder(root *TreeNode, m map[*TreeNode]*node) int {
if root == nil {
return 0
}
lcnt := inorder(root.Left, m)
n := &node{ index: len(m), lcnt: lcnt }
m[root] = n
n.rcnt = inorder(root.Right, m)
return lcnt + n.rcnt + 1
}
func lowestCommonAncestor(root, l, r *TreeNode) *TreeNode {
m := map[*TreeNode]*node{}
// collect subtree info
inorder(root, m)
if m[l].index > m[r].index {
l, r = r, l
}
isValid := func(n *TreeNode) bool {
if n == nil {
return false
}
ns := m[n]
if ns.index - ns.lcnt <= m[l].index && ns.index + ns.rcnt >= m[r].index {
return true
}
return false
}
res := root
for {
if isValid(res.Left) {
res = res.Left
} else if isValid(res.Right) {
res = res.Right
} else {
break
}
}
return res
}