Leetcode专题-236-二叉树的最近公共祖先
文章目录
力扣链接:
https://leetcode.cn/problems/lowest-common-ancestor-of-a-bina...
解题思路:
使用递归的方式进行后序遍历,当遍历到某个节点时,分别递归查找它的左右子树,如果左子树和右子树都返回非空值,则说明当前节点就是p和q的最近公共祖先,直接返回当前节点。如果左子树返回的值为空,则说明p和q都在右子树中,直接返回右子树返回的值。如果右子树返回的值为空,则说明p和q都在左子树中,直接返回左子树返回的值。最终,递归结束后返回的节点即为p和q的最近公共祖先
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == p || root == q || root == nil {
return root
}
left := lowestCommonAncestor(root.Left, p, q)
right := lowestCommonAncestor(root.Right, p, q)
if left != nil && right != nil {
return root
}
if left == nil {
return right
}
return left
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论