当前位置:网站首页>LeetCode:236. The nearest common ancestor of binary tree
LeetCode:236. The nearest common ancestor of binary tree
2022-07-06 08:51:00 【Bertil】
Given a binary tree , Find the nearest common ancestor of the two specified nodes in the tree .
In Baidu Encyclopedia, the most recent definition of public ancestor is :“ For a tree T Two nodes of p、q, The nearest common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible ( A node can also be its own ancestor ).”
Example 1:
Input :root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output :3
explain : node 5 And nodes 1 The most recent public ancestor of is the node 3 .
Example 2:
Input :root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output :5
explain : node 5 And nodes 4 The most recent public ancestor of is the node 5 . Because by definition, the nearest common ancestor node can be the node itself .
Example 3:
Input :root = [1,2], p = 1, q = 2
Output :1
Tips :
- The number of nodes in the tree is in the range [2, 10^5] Inside .
- -10^9 <= Node.val <= 10^9
- all Node.val Different from each other .
- p != q
- p and q All exist in a given binary tree .
Their thinking
1. First use recursion :root yes null perhaps root be equal to p or q, explain root yes p,q The common ancestor of ( Recursion ends ), So as to recurse the left and right subtrees
2. Then judge after the recursion of the left and right subtrees
- If the left and right subtree recursive functions do not return empty , be root Namely p,q The common ancestor of
- If the value returned by the left subtree recursive function is null , be p,q All in the right subtree , Go straight back to right that will do
- If the value returned by the right subtree recursive function is null , be p,q It's all in zuozhu , Go straight back to left that will do
Code
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
/** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */
var lowestCommonAncestor = function(root, p, q) {
const travelTree = function(root, p, q) {
// Recursive termination condition
if(root === null || root === p|| root === q) {
return root;
}
let left = travelTree(root.left, p, q);
let right = travelTree(root.right, p, q);
// If you can find both the left and right subtrees of a node p and q, This indicates that this node is a common ancestor
if(left !== null && right !== null) {
return root;
}
if(left === null) {
return right;
}
return left;
}
return travelTree(root, p, q);
};
边栏推荐
猜你喜欢
JS native implementation shuttle box
Visual implementation and inspection of visdom
marathon-envs项目环境配置(强化学习模仿参考动作)
Problems in loading and saving pytorch trained models
Using pkgbuild:: find in R language_ Rtools check whether rtools is available and use sys The which function checks whether make exists, installs it if not, and binds R and rtools with the writelines
Target detection - pytorch uses mobilenet series (V1, V2, V3) to build yolov4 target detection platform
Charging interface docking tutorial of enterprise and micro service provider platform
sublime text没关闭其他运行就使用CTRL+b运行另外的程序问题
vb.net 随窗口改变,缩放控件大小以及保持相对位置
[MySQL] limit implements paging
随机推荐
gcc动态库fPIC和fpic编译选项差异介绍
如何有效地进行自动化测试?
生成器参数传入参数
Analysis of the source code of cocos2d-x for mobile game security (mobile game reverse and protection)
vb.net 随窗口改变,缩放控件大小以及保持相对位置
C language double pointer -- classic question type
随手记01
LeetCode:124. 二叉树中的最大路径和
Swagger setting field required is mandatory
ESP8266-RTOS物联网开发
[embedded] cortex m4f DSP Library
win10系统中的截图,win+prtSc保存位置
软件压力测试常见流程有哪些?专业出具软件测试报告公司分享
[MySQL] limit implements paging
opencv+dlib实现给蒙娜丽莎“配”眼镜
CSP first week of question brushing
LeetCode:剑指 Offer 48. 最长不含重复字符的子字符串
优秀的软件测试人员,都具备这些能力
LeetCode:34. 在排序数组中查找元素的第一个和最后一个位置
LeetCode:214. 最短回文串