代码编织梦想

题目

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

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

示例 1:

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

出现公共祖先的情况:

  • 节点A的左孩子是B,右孩子是C,那么A就是B和C的最近公共祖先。
  • 节点B的左孩子是C,那么节点B就是B和C的最近公共祖先。
  • 节点B的右孩子是C,那么节点B就是B和C的最近公共祖先。

用什么方法,可以找到某节点的做孩子,右孩子,还能返回该节点呢?当找到一个节点的左孩子是p(q),右孩子是q§,那就返回这个节点就好了。如果是第二和三的情况,找到p或q其中一个,返回的节点也就是最小公共祖先了。
代码要遍历整棵树,因为要对返回值做判断。比如:

  • 递归遍历左子树为p,递归遍历右子树为q,那说明最小公共祖先就是根节点了。
  • 递归遍历左子树为空,那最小公共祖先就是递归遍历右子树的返回值。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null && right != null) {
            return right;
        } else if(left != null && right == null) {
            return left;
        } else if(left == null && right == null){
            return null;
        } else {
            return root;
        }
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_42373606/article/details/129493306

leetcode 二叉树的最近公共祖先(java)_藏呆羊的博客-爱代码爱编程

Leetcode汇总贴: leetcode经典编程题目(Java实现) leetcode题目 二叉树的最近公共祖先 -- leetcode 236 题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖

C++实现二叉树的最近公共祖先-爱代码爱编程

一、问题描述(236. 二叉树的最近公共祖先) 二、AC代码如下(解释见注释) 关键: ①精确定义什么是祖先,什么是最近公共祖先(描述清楚问题是解决问题的第一步) ②由于需要从下往上遍历,自然选择后序遍历 class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root,

二叉树最近公共祖先递归算法-爱代码爱编程

二叉树最近公共祖先递归算法 我目前搜到的网上的版本都是这样的; BTree NearestAncestor(BTree T,BTree p,BTree q){ if(T==NULL||T==p||T==q) return T; BTree left = NearestAncestor(T->lchild,p,q); BTree righ

Java 求解二叉树的最近公共祖先-爱代码爱编程

文章目录 一、题目二、分析三、代码四、总结 一、题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉树: root =

二叉树寻找祖先C语言,二叉树寻找最近公共祖先节点-爱代码爱编程

方法一:递归 1.思路 (1)定义fx表示x节点的子树中是否包含p或者q节点,如果包含为true,否则为false。那么符合条件的最近公共祖先节点一定满足下面的条件: (flson && frson) || ((x = p || x = q) && (flson || frson)) 其中flson和frson分

算法入门: 二叉树最近公共祖先-爱代码爱编程

题目: 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。注意如果节点p为另一个节点q的子节点。那么最近 公共父节点为q。 题目分析: 1、找 p、q两个节点,可采用深度优先或者广度优先 2、找公共父节点。采用深度优先。 找联系 1)p,q 和公共父节点都可采用深度优先。因此遍历策略采用深度优先。 2)因为公共父节点

二叉树的最近公共祖先-爱代码爱编程

假设我们需要找到结点p,q的最近公共祖先,我们可以发现二叉树的最近公共祖先满足:此结点的左结点和右节点分别存在p,q或者此节点恰好是p,q之一并且他的左右结点之一恰好是另一结点。我们假设fleft==true表示左节点或左节点的子节点中存在其中一个元素,fleft == false则表示左节点或左节点的子节点中不存在元素,fright同理,则判断一个结

二叉树最近公共祖先相关题目(Leetcode题解-Python语言)-爱代码爱编程

236. 二叉树的最近公共祖先 class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': def dfs(root: 'TreeNode', p: 'TreeNo

JAVA练习121- II. 二叉树的最近公共祖先-爱代码爱编程

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

leetcode-1590. 使数组和能被 p 整除【前缀和,哈希表】-爱代码爱编程

LeetCode-1590. 使数组和能被 P 整除【前缀和,哈希表】 题目描述:解题思路一:前缀和,具体看注释。解题思路二:在遍历过程中计算前缀和解题思路三:0 题目描述: 给你一个正整数数组 nums,请

leetcode每日一题(1388. pizza with 3n slices)-爱代码爱编程

There is a pizza with 3n slices of varying size, you and your friends will take slices of pizza as follows: You

leetcode:406按照身高和体重排序:-爱代码爱编程

406. 根据身高重建队列 假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。 请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 que

二叉树最近公共祖先-爱代码爱编程

给定一颗二叉树以及两个节点,查找两个节点最近的公共祖先,有可能公共祖先是两个节点中的其中一个 比如给定D,E两个节点,其最近的公共祖先为B 非递归方式 层次遍历找到两个节点,遍历过程中,将每个节点以及它的父节点放到Map中

java二叉树的最近公共祖先_java获取二叉树的公共祖先-爱代码爱编程

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” /** * Definition for a binary tree node. * public c

【leetcode】剑指 offer(19)-爱代码爱编程

目录 题目:剑指 Offer 36. 二叉搜索树与双向链表 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 题目:剑指 Offer 36. 二叉搜索树与双向链表 - 力扣(Leetcode) 题目的接口: /* // Definition for a Node. class Node {