236. Lowest Common Ancestor of a Binary Tree

2023-12-21 15:48

本文主要是介绍236. Lowest Common Ancestor of a Binary Tree,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

236. Lowest Common Ancestor of a Binary Tree

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

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

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

 

示例 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 为不同节点且均存在于给定的二叉树中。

解法一:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool findNode(TreeNode* root, TreeNode* p) {if (!root) return false;if (root == p) return true;return findNode(root->left, p) || findNode(root->right, p);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {TreeNode* cur = root;while (true) {if (cur == p || cur == q) return cur;bool b1 = findNode(cur->left, p);  // p在左子树吗bool b2 = findNode(cur->left, q);  // q在左子树吗if (b1 && b2) cur = cur->left;  // 同在左侧else if (!b1 && !b2) cur = cur->right;  // 同在右侧else return cur;  // 分别在两侧}return nullptr;}
};

解法二:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:// 如果找到了返回true.bool getPath(vector<TreeNode*>& vec, TreeNode* root, TreeNode* p) {if (!root) return false;if (root == p) {vec.push_back(p);return true;}vec.push_back(root);if (getPath(vec, root->left, p) ||getPath(vec, root->right, p)) return true;vec.pop_back();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {vector<TreeNode*> v1, v2;getPath(v1, root, p);getPath(v2, root, q);for (auto i = v1.rbegin(); i != v1.rend(); ++i) {for (auto j = v2.rbegin(); j != v2.rend(); ++j) {if (*i == *j) return *i;}}return *v1.begin();}
};

解法一:每次判断p、q结点位于左、右哪一颗子树上。如果在同侧,就向该侧前进;如果在两侧,说明就是当前结点。每次都要遍历查找比较耗时。

解法二:先遍历找出p、q结点的路径v1、v2,再从后向前查找v1、v2中首个相同的元素,返回即可。

2020/07/03 12:07

这篇关于236. Lowest Common Ancestor of a Binary Tree的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/520574

相关文章

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

树(Tree)——《啊哈!算法》

树 什么是树?树是一种特殊的图,不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点,那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点(祖先)。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶

226 Invert Binary Tree

//226 Invert Binary Tree//算法思路:主要使用递归算法public class Solution {public TreeNode invertTree(TreeNode root) {//1 出口 空节点if (root==null)return null;//2 递归 调用自己TreeNode left = root.left;TreeNode right = ro

兔子--Android Studio出现错误:Error:Execution failed for task ':myapp:dexDebug'. com.android.ide.common.pro

重点在:finished with non-zero exit value 2. 这里表明了有重复的内容存在。 由于:Android Studio中引入包的方式有如下2种:    compile 'com.android.support:support-v4:22.0.0'    compile files('libs/support-v

YOLOV5入门教学-common.py文件

在 YOLOv5 框架中,common.py 文件是一个核心组件,负责定义深度学习模型的基础模块和常用操作。无论是卷积层、激活函数、特征融合还是其他复杂的模型结构,common.py 都提供了灵活且高效的实现。在这篇文章中,我们将深入解析 common.py 的设计思想、各个模块的功能以及它在 YOLOv5 中的应用。通过理解该文件的实现细节,不仅可以帮助我们更好地掌握 YOLOv5 的内部结构,

Sorry!Hbase的LSM Tree就是可以为所欲为!

我们先抛出一个问题: LSM树是HBase里使用的非常有创意的一种数据结构。在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中,则是使用日志结构合并树(Log-structured Merge Tree,LSM Tr

【spring】does not have member field ‘com.sun.tools.javac.tree.JCTree qualid

spring-in-action-6-samples 的JDK版本 最小是11,我使用 了22: jdk21 jdk22 都与lombok 不兼容,必须使用兼容版本, 否则报错: thingsboard 的大神解释了: java: java.lang.NoSuchFieldError: Class com

[LeetCode] 863. All Nodes Distance K in Binary Tree

题:https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/ 题目大意 求给树中,距给定 结点 指定长度的 所有结点的val 思路 tree -> graph 、 bfs 先遍历树,并用map记录每个结点的父结点 ,将树变为图,然后 bfs。 /*** Definition for a binary tree

js实现树级递归,通过js生成tree树形菜单(递归算法)

1、效果图 需求:首先这是一个数据集—js的类型,我们需要把生成一个tree形式的对象 : var data = [{ id: 1, name: "办公管理", pid: 0 },{ id: 2, name: "请假申请", pid: 1 },{ id: 3, name: "出差申请", pid: 1 },{ id: 4, name: "请假记录", pid: 2 },{ id:

【unity实战】利用Root Motion+Blend Tree+Input System+Cinemachine制作一个简单的角色控制器

文章目录 前言动画设置Blend Tree配置角色添加刚体和碰撞体代码控制人物移动那么我们接下来调整一下相机的视角效果参考完结 前言 Input System知识参考: 【推荐100个unity插件之18】Unity 新版输入系统Input System的使用,看这篇就够了 Cinemachine虚拟相机知识参考: 【推荐100个unity插件之10】Unity最全的最详细的C