107、【树与二叉树】leetcode ——236. 二叉树的最近公共祖先:回溯法(C++版本)
2023-09-11 14:20:01 时间
题目描述
解题思路
p和q可能会出现两种情况:
(1)p和q分别在左、右子树中,此时返回最近公共祖先结点;
(2)p和q在同一侧子树中,此时谁为祖先结点返回谁。
回溯法
自底向上的返回信息,采用后序遍历的方式。当从左孩子或右孩子中找到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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 遍历到空节点返回NULL,找到q或者p返回root。注意当出现情况二时,先找到谁,一定会先返回谁。
if(!root || root == p || root == q) return root;
// 左右
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
// 中:当左和右都不为NULL,说明当前为公共祖先,返回root
if(left && right) return root;
// 当一侧为零,另一侧不为零,返回孩子
else if(!left) return right;
return left;
}
};
参考文章:
236. 二叉树的最近公共祖先
相关文章
- C++对象模型——继承体系下的对象构造(第五章)
- qt实现web服务器加载vue应用进行C++和html混合编程-连载【6】-企业级系统开发实战连载系列 -技术栈(vue、element-ui、qt、c++、sqlite)
- c++中cin的基本使用方法
- C/C++glob函数遍历文件夹所有文件
- 基于C++开发的(控制台)万年历系统【100010447】
- 【C/C++内存分布】
- 187、【栈与队列】leetcode ——42. 接雨水(C++版本)
- 183、【动态规划】leetcode ——516. 最长回文子序列(C++版本)
- 180、【动态规划】leetcode ——583. 两个字符串的删除操作:两种动态规划思路(C++版本)
- 175、【动态规划】leetcode ——718. 最长重复子数组 (C++版本)
- 134、【贪心算法】leetcode ——134. 加油站(贪心策略)(C++版本)
- 118、【回溯算法】leetcode ——40. 组合总和 II:回溯法+剪枝优化(C++版本)
- 112、【树与二叉树】leetcode ——108. 将有序数组转换为二叉搜索树:二分查找树(C++版本)
- 110、【树与二叉树】leetcode ——450. 删除二叉搜索树中的节点:递归法+迭代法(C++版本)
- 108、【树与二叉树】leetcode ——235. 二叉搜索树的最近公共祖先:普通树解法+BST性质解法(C++版本)
- 104、【树与二叉树】leetcode ——98. 验证二叉搜索树:递归法[先序+中序+后序]+迭代法(C++版本)
- 102、【树与二叉树】leetcode ——654. 最大二叉树(C++版本)
- 100、【树与二叉树】leetcode ——105. 从前序与中序遍历序列构造二叉树+106. 从中序与后序遍历序列构造二叉树(C++版本)
- 92、【树与二叉树】leetcode ——111. 二叉树的最小深度:层次遍历+先序DFS+后序DFS[子问题分解](C++版本)
- 86、【栈与队列】leetcode ——39. 滑动窗口最大值:单调队列+滑动窗口(C++版本)
- 79、【字符串】leetcode ——28. 找出字符串中第一个匹配项的下标(C++版本)
- 67、【哈希表】leetcode——242. 有效的字母异位词(C++版本)
- 大话设计模式C++实现-第17章-适配器模式
- 《C++ Primer Plus》学习笔记11
- C++学习笔记11-面向对象2