版权声明:原创勿转 https://cloud.tencent.com/developer/article/1412922
寻找最近的公共祖先,当root非空时可以区分为三种情况:1)两个节点均在root的左子树,此时对root->left递归求解;2)两个节点均在root的右子树,此时对root->right递归求解;3)两个节点分别位于root的左右子树,此时LCA为root。
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == nil {
return nil
}
for root != nil {
if p.Val > root.Val && q.Val > root.Val {
root = root.Right
} else if p.Val < root.Val && q.Val < root.Val {
root = root.Left
} else {
return root
}
}
return nil
}