申办网站流程,铜川免费做网站公司,互联网个人信用信息服务平台,wordpress html音乐LeetCode 热题 100_二叉树的最近公共祖先#xff08;49_236#xff09; 题目描述#xff1a;输入输出样例#xff1a;题解#xff1a;解题思路#xff1a;思路一#xff08;深度优先搜索#xff09;#xff1a; 代码实现代码实现#xff08;思路一#xff08;深度优… LeetCode 热题 100_二叉树的最近公共祖先49_236 题目描述输入输出样例题解解题思路思路一深度优先搜索 代码实现代码实现思路一深度优先搜索以思路一为例进行调试 题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。”
输入输出样例
示例 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 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3 输入root [1,2], p 1, q 2 输出1
提示 树中节点数目在范围 [2, 105] 内。 -109 Node.val 109 所有 Node.val 互不相同 。 p ! q p 和 q 均存在于给定的二叉树中。
题解
解题思路
思路一深度优先搜索
1、在解决此问题时我们首先应该讨论一下pq在二叉树中的各个分布情况。假设一个结点为root为当前遍历的结点。 递归出口 ① root结点为null则返回递归出口(返回null) ② 当前结点为p,返回p第一次发现p且未找到q(返回当前结点因当前结点可能为祖先) 为什么直接返回呢因为我们可以通过遍历除p的子孙节点外的其他结点来判断q的位置若其他结点中存在q则p不是q的祖先。若其他结点不存在q则q是p的子孙p为公共祖先结点 ③ 当前结点为q,返回q第一次发现q且未找到p(返回当前结点因当前结点可能为祖先) 为什么直接返回呢因为我们可以通过遍历除q的子孙节点外的其他结点来判断p的位置若其他结点存在p则q不是p的祖先。若其他结点不存在p则p是q的子孙q为公共祖先结点
递归体 按深度优先遍历递归的寻找左右子树。
判断当前节点的左右子树左右子树遍历完后 ① 当前结点左右子树都没有查找到p或q。返回null ② 当前结点左子树找到一个结点(p或q),右子树找到一个结点(p或q)。(返回当前结点当前结点为公共祖先) ③当前结点左子树找到一个结点(p或q)右子树没找到。(返回左子树找到的结点) ④ 当前结点右子树找到一个结点(p或q)左子树没找到。(返回右子树找到的结点)
2、复杂度分析 ① 时间复杂度O(n)n代表二叉树中结点的个数最坏的情况会遍历整颗二叉树。 ② 空间复杂度O(n)采用的是深度遍历搜索所以需要用到函数栈最坏情况下为O(n)。
代码实现
代码实现思路一深度优先搜索
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//遍历到nullptr或者p、 q则返回if (rootnullptr||rootp||rootq) return root;//递归的进行查找TreeNode *leftlowestCommonAncestor(root-left,p,q);TreeNode *rightlowestCommonAncestor(root-right,p,q);//如果当前结点的左右子树都没查找到q或p则返回nullptrif(leftnullptrrightnullptr) return nullptr;//查找到p、q的公共祖先则返回该结点if (left!nullptrright!nullptr) return root;//p或q存在左子树则返回左子树对应的结点if (left!nullptr) return left;//p或q存在右子树则返回右子树对应的结点return right;
}以思路一为例进行调试
#includeiostream
#include vector
#include queue
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};//通过数组创建二叉树-1代表nullptr;
TreeNode *createTree(vectorint nums){if (nums.empty()){return nullptr;}queueTreeNode * q;TreeNode *rootnew TreeNode(nums[0]);q.push(root);int i1;while (inums.size()){TreeNode *nodeq.front();q.pop();if (inums.size()nums[i]!-1){node-leftnew TreeNode(nums[i]);q.push(node-left);}i;if (inums.size()nums[i]!-1){node-rightnew TreeNode(nums[i]);q.push(node-right);}i;}return root;
}//用于检查二叉树是否创建正确
void inorderTraversal(TreeNode *root){if (rootnullptr){return ;}inorderTraversal(root-left);coutroot-val ;inorderTraversal(root-right);
}//二叉树的最近公共祖先
class Solution
{
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//遍历到nullptr或者p、 q则返回if (rootnullptr||rootp||rootq) return root;//递归的进行查找TreeNode *leftlowestCommonAncestor(root-left,p,q);TreeNode *rightlowestCommonAncestor(root-right,p,q);//如果当前结点的左右子树都没查找到q或p则返回nullptrif(leftnullptrrightnullptr) return nullptr;//查找到p、q的公共祖先则返回该结点if (left!nullptrright!nullptr) return root;//p或q存在左子树则返回左子树对应的结点if (left!nullptr) return left;//p或q存在右子树则返回右子树对应的结点return right; }
};int main(int argc, char const *argv[])
{//-1代表nullvectorint nums{3,5,1,6,2,0,8,-1,-1,7,4};//通过nums数组创建二叉树TreeNode *rootcreateTree(nums);//用于检查二叉树是否创建正确//inorderTraversal(root);//计算root-left和root-right的最近公共祖先Solution s;TreeNode *ans s.lowestCommonAncestor(root,root-left,root-right);coutans-val;return 0;
}
LeetCode 热题 100_二叉树的最近公共祖先49_236)原题链接 欢迎大家和我沟通交流(✿◠‿◠)
