专栏首页爱写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 236.二叉树的最近公共祖先】双解法:递归实现 + 利用父指针

    这题相较于 LeetCode 235.二叉搜索树的最近公共祖先 的递归思考起来比较有难度。

    心谭博客
  • 235. Lowest Common Ancestor of a Binary Search Tree(Tree-Easy)

    Given a binary search tree (BST), find the lowest common ancestor (LCA) of two g...

    Jack_Cui
  • ​LeetCode刷题实战235:二叉搜索树的最近公共祖先

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • Js算法与数据结构拾萃(4):二叉树

    因此只要答对这道题,你就可以超越世界级大牛,问鼎码林之巅(逃) 导读: •二叉树知识重点•二叉树深度不一,因此天生适用递归,因此可用递归处理•判断两树相等•翻转...

    一粒小麦
  • Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

    Given a binary search tree (BST), find the lowest common ancestor (LCA) of two ...

    triplebee
  • 【LeetCode 235.二叉搜索树的最近公共祖先】JavaScript/C++实现

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

    心谭博客
  • LeetCode笔记:235. Lowest Common Ancestor of a Binary Search Tree

    image.png For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. A...

    Cloudox
  • 【LeetCode】235. Lowest Common Ancestor of a Binary Search Tree 公共祖先

    Given a binary search tree (BST), find the lowest common ancestor (LCA) of two g...

    韩旭051
  • GitHub高星!互联网公司最常见的面试算法题大集合

    LeetCode是一个美国的在线编程网站,收集了各个大厂的笔试面试题,对找工作的毕业生和开发者来说,非常有价值。不过LeetCode上面的题目很多都是考察应聘者...

    新智元
  • Tree - 235. Lowest Common Ancestor of a Binary Search Tree

    235. Lowest Common Ancestor of a Binary Search Tree

    用户5705150
  • Leetcode 236. Lowest Common Ancestor of a Binary Tree

    根据LCA的定义,二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点,LCA的定义没什么好解释的,主要是这道题的解法。   我们要找p和q的最小公共...

    xindoo
  • 【Leetcode235】关关的刷题日记66 –Lowest Common Ancestor of a BST

    关关的刷题日记66 – Leetcode 235 Lowest Common Ancestor of a Binary Search Tree 题目 ? 题目的...

    WZEARW
  • 二叉树-LeetCode 235、236、226、230(中序,LCA,DFS)

    给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 ...

    算法工程师之路
  • 二叉树-最近的公共祖先

    已知二叉树,求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u,满足在树上最低(离根最 远),且v,w两个节点都是u的子孙。...

    小飞侠xp
  • 资源 | 从算法到数据结构,百道面试问题实现答案集合

    选自GitHub 作者:Sherali Obidov 机器之心编译 参与:李亚洲、微胖、蒋思源 该资源是算法、数据结构以及面试问题解决方案的集合,里面的 rep...

    机器之心
  • Leetcode 236. Lowest Common Ancestor of a Binary Tree

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

    triplebee
  • leetcode树之二叉搜索树的最近公共祖先

    这里采用递归的思路,并利用二叉搜索树的特性来解题;针对root.val大于p.val及q.val的递归执行lowestCommonAncestor(root.l...

    code4it
  • Tree - 236. Lowest Common Ancestor of a Binary Tree

    236. Lowest Common Ancestor of a Binary Tree

    用户5705150
  • 【leetcode刷题】T131-二叉搜索树的最近公共祖先

    https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

    木又AI帮

扫码关注云+社区

领取腾讯云代金券