当前位置:网站首页>Finding the nearest common ancestor of binary tree by recursion
Finding the nearest common ancestor of binary tree by recursion
2022-07-06 00:51:00 【Hydrion-Qlz】
236. The nearest common ancestor of a binary tree
difficulty : secondary
Given a binary tree , Find the nearest common ancestor of the two specified nodes in the tree .
Baidu Encyclopedia The definition of the most recent common ancestor in 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 ).
Ideas
If you can't understand this question, you can have a look first Find the nearest common ancestor of binary search tree
There are three situations
- Both nodes are smaller than the current node , Are all on the left subtree of the current node
- Both nodes are larger than the current node , Are all on the right subtree of the current node
- One is larger than the current node ( be equal to ), One is smaller than the current node ( be equal to ), Then the current node is the nearest common ancestor of the two nodes
But if it is implemented, we cannot judge whether it is on the left or right of the current node according to the value of the current node
So we can only traverse all subtrees of the current node , See if you can find at least one node on its left or right
- If the current node is equal to one of the nodes , Then return directly
- If there is a node on the left side and a node on the right side , It means that the current node is the nearest public child node
- If both are on one side , Then the nearest one must be at a node on that side
package cn.edu.xjtu.carlWay.tree.commonAncestor;
import cn.edu.xjtu.Util.TreeNode.TreeNode;
/** * 236. The nearest common ancestor of a binary tree * Given a binary tree , Find the nearest common ancestor of the two specified nodes in the tree . * <p> * 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 ).” * <p> * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/ */
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
// The node and its subtree must contain at least one node
if (root.val == p.val || root.val == q.val) {
return root;
}
// Judge whether the left and right subtrees of the current node contain at least one node
TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
if (leftNode != null && rightNode != null) {
// If both the left subtree and the right subtree contain a node , It means that the current node is the nearest public child node
return root;
} else {
// Otherwise, the two must not do null The other side of the
return leftNode == null ? rightNode : leftNode;
}
}
}
边栏推荐
- Reading notes of the beauty of programming
- [EI conference sharing] the Third International Conference on intelligent manufacturing and automation frontier in 2022 (cfima 2022)
- 关于#数据库#的问题:(5)查询库存表中每本书的条码、位置和借阅的读者编号
- Cannot resolve symbol error
- 数据分析思维分析方法和业务知识——分析方法(二)
- Leetcode 44 Wildcard matching (2022.02.13)
- Spark SQL空值Null,NaN判断和处理
- [groovy] JSON serialization (jsonbuilder builder | generates JSON string with root node name | generates JSON string without root node name)
- logstash清除sincedb_path上传记录,重传日志数据
- 测试/开发程序员的成长路线,全局思考问题的问题......
猜你喜欢
[EI conference sharing] the Third International Conference on intelligent manufacturing and automation frontier in 2022 (cfima 2022)
从 1.5 开始搭建一个微服务框架——调用链追踪 traceId
Cve-2017-11882 reappearance
看抖音直播Beyond演唱会有感
[groovy] XML serialization (use markupbuilder to generate XML data | create sub tags under tag closures | use markupbuilderhelper to add XML comments)
cf:C. The Third Problem【关于排列这件事】
OpenCV经典100题
Fibonacci number
Folding and sinking sand -- weekly record of ETF
Analysis of the combination of small program technology advantages and industrial Internet
随机推荐
Arduino hexapod robot
NLP text processing: lemma [English] [put the deformation of various types of words into one form] [wet- > go; are- > be]
Classic CTF topic about FTP protocol
【EI会议分享】2022年第三届智能制造与自动化前沿国际会议(CFIMA 2022)
How spark gets columns in dataframe --column, $, column, apply
Leetcode 44 Wildcard matching (2022.02.13)
程序员搞开源,读什么书最合适?
Zhuhai's waste gas treatment scheme was exposed
小程序容器可以发挥的价值
Set data real-time update during MDK debug
【线上小工具】开发过程中会用到的线上小工具合集
2022-02-13 work record -- PHP parsing rich text
Four dimensional matrix, flip (including mirror image), rotation, world coordinates and local coordinates
Idea remotely submits spark tasks to the yarn cluster
免费的聊天机器人API
Keepalive component cache does not take effect
Spark AQE
毕设-基于SSM高校学生社团管理系统
OpenCV经典100题
[groovy] JSON serialization (jsonbuilder builder | generates JSON string with root node name | generates JSON string without root node name)