专栏首页爱写Bug二叉树的最近公共祖先 Lowest Common Ancestor of a Binary Tree

二叉树的最近公共祖先 Lowest Common Ancestor of a Binary Tree

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

img

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉树中。

Note:

  • All of the nodes' values will be unique.
  • p and q are different and both values will exist in the binary tree.

解题思路:

只要熟悉树的遍历,应该都可以迅速完成该题。

关键点:

  • 如果在 node 的左子树没找到与 p,q 相等的结点,递归函数返回null,公共祖先在右侧结点
  • 如果在 node 的右子树没找到与 p,q 相等的结点,递归函数返回null,公共祖先在左侧结点
  • 如果在 node 左右子树都找到与 p,q 相等的结点,递归函数返回公众祖先 node 结点

下面展示广度优先搜索的递归解法。

Java:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 基线条件
        if (root == null || root == p || root == q)
            return root;
        // 最小公共结点在左子树或右子树的情况
        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
        // 左子树或右子树未找到与 p,q 相等的结点时最小公共祖先在另一侧
        if (leftNode == null)
            return rightNode;
        if (rightNode == null)
            return leftNode;

        return root;
    }
}

Python:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root.val == p.val or root.val == q.val:
            return root
        left_node = self.lowestCommonAncestor(root.left, p, q)
        right_node = self.lowestCommonAncestor(root.right, p, q)

        if not left_node:
            return right_node
        if not right_node:
            return left_node

        return root

Golang:

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root.Val == p.Val || root.Val == q.Val {
        return root
    }
    leftNode := lowestCommonAncestor(root.Left, p, q)
    rightNode := lowestCommonAncestor(root.Right, p, q)

    if leftNode == nil {
        return rightNode
    }
    if rightNode == nil {
        return leftNode
    }
    return root
}

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 700: 二叉搜索树中的搜索 Search in a Binary Search Tree

    给定二叉搜索树(BST)的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在,则返回 NULL。

    爱写bug
  • LeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST

    给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节...

    爱写bug
  • LeetCode 701: 二叉搜索树中的插入操作 Insert into a Binary Search Tree

    给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。

    爱写bug
  • 浏览器环境检测

    本文是直接把seleniumpyppeteer 以及正常打开浏览器 的环境差异直接列出来

    爬虫
  • 【趣学程序】Linux流的重定向

    趣学程序-shaofeer
  • 二叉树:删除节点

    https://leetcode-cn.com/problems/delete-node-in-a-bst/

    灰子学技术
  • 剑指Offer - 面试题54. 二叉搜索树的第k大节点(二叉树循环遍历)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kd...

    Michael阿明
  • Golang Leetcode 669. Trim a Binary Search Tree.go

    更多内容请移步我的repo:https://github.com/anakin/golang-leetcode

    anakinsun
  • 利用rbd命令把 ceph pool 中的一个镜像导出

    查看镜像 [root@node1 ~]# rbd ls images a56330e7-79d7-4639-a68f-366ac344bfe2 eccfee07...

    院长技术
  • Linux工作目录切换命令

    心跳包

扫码关注云+社区

领取腾讯云代金券