LeetCode 剑指offer 68【二叉树的最近公共祖先】
2023-09-11 14:17:55 时间
思路
一般情况下,对于一颗树root
来说,如果节点p、q
分别分布在root
的左右子树中,那么节点p、q
的最近公共祖先为root
;对于特殊的情况,即p、q
均只分布在root
的一侧(左子树或者是右子树)中,我们则可以递归的处理相同的问题,即在一颗子树(root->left
或者root->right
)中判断节点p、q
的最近公共祖先。
细节处理
- 在递归的过程中,如果遇到空节点(
root == nullptr
),我们可以断定此时必定返回的祖先节点是nullptr
,因为此时的树已经为空,找不到祖先节点,也就可以认为祖先节点为空; - 在递归的过程中,如果当前子树的根节点
root
(或者说是当前遍历到的节点)为p、q
中的某一个时,由于题干保证树中每一个节点都不相同,所以此时root == p
和root == q
只会有一个为真,并且当前节点root
为需要判定祖先的某一个节点时,我们假设出两种情况①:另外一个需要判断祖先的节点在当前root
的子树中,那么节点p、q
的最近公共祖先就是root
,②:另外一个需要判断祖先的节点不在当前root
的子树中,我们返回当前当前节点root
的祖先root
(非空节点自身也是自己的祖先),综上我们可以直接返回root
.
时间复杂度
O ( N ) O(N) O(N) (每一个节点我们最多只会访问一次)
C++代码
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return nullptr;
if(root == p || root == q) return root;
auto left = lowestCommonAncestor(root->left, p, q);
auto right = lowestCommonAncestor(root->right, p, q);
if(left && right) return root;
if(left) return left;
return right;
}
};
相关文章
- Java实现 LeetCode 814 二叉树剪枝 (遍历树)
- Java实现 LeetCode 662 二叉树最大宽度(递归)
- Java实现 LeetCode 659 分割数组为连续子序列 (哈希)
- Java实现 LeetCode 606 根据二叉树创建字符串(遍历树)
- Java实现 LeetCode 498 对角线遍历
- Java实现 LeetCode 385 迷你语法分析器
- Java实现 LeetCode 543 二叉树的直径
- Java实现 LeetCode 101 对称二叉树
- Java实现 LeetCode 107 二叉树的层次遍历 II(二)
- Java实现 LeetCode 106 从中序与后序遍历序列构造二叉树
- LeetCode:111_Minimum Depth of Binary Tree | 二叉树的最小深度 | Easy
- LeetCode: 102_Binary Tree Level Order Traversal | 二叉树自顶向下的层次遍历 | Easy
- LeetCode-面试题 05.02. 二进制数转字符串【数学,字符串,位运算】
- ( “树” 之 BFS) 637. 二叉树的层平均值 ——【Leetcode每日一题】
- 168. Excel表列名称——【Leetcode每日一题】
- Leetcode学习计划之动态规划入门day16(64,221)
- Leetcode 74. 搜索二维矩阵
- Leetcode 228. 汇总区间(可以,已解决)
- LeetCode:Reverse Integer
- Leetcode--Two Sum
- LeetCode 二叉树/n叉树的解题思路
- leetcode 453. Minimum Moves to Equal Array Elements
- 【Leetcode刷题Python】239. 滑动窗口最大值
- 【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
- LeetCode 101. 对称二叉树