【LeetCode】236. 二叉树的最近公共祖先、 JZ36 二叉搜索树与双向链表-阿里云开发者社区

【LeetCode】236. 二叉树的最近公共祖先、 JZ36 二叉搜索树与双向链表

2023-10-11 37

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 236. 二叉树的最近公共祖先236. 二叉树的最近公共祖先题目描述：

作者：小卢

专栏：《Leetcode》

喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》

236. 二叉树的最近公共祖先

题目描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例：

思路：

我们这里利用两个栈来存储p和q的路径，让将问题转换为链表相交问题

让大的先走差值步，然后同时走找到相同的节点返回

代码：

1. class Solution {
2. public:
3. bool GetPath(TreeNode*root,TreeNode*x,stack<TreeNode*>&Path)
4.         {
5. if(root==nullptr)
6. return false;
7.             Path.push(root);
8. if(x==root)
9. return true;
10. 
11. if(GetPath(root->left,x,Path))
12. return true;
13. if(GetPath(root->right,x,Path))
14. return true;
15.             Path.pop();
16. return false;
17. 
18.         }
19. 
20. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
21.         stack<TreeNode*>pPath,qPath;
22. GetPath(root,p,pPath);
23. GetPath(root,q,qPath);
24. while(pPath.size()!=qPath.size())
25.         {
26. if(pPath.size()>qPath.size())
27.             pPath.pop();
28. else
29.             qPath.pop();
30.         }
31. while(pPath.top()!=qPath.top())
32.         {
33.             pPath.pop();
34.             qPath.pop();
35.         }
36. return pPath.top();
37.     }
38. };

JZ36 二叉搜索树与双向链表

二叉搜索树与双向链表_牛客题霸_牛客网

题目描述：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n)

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继

2.返回链表中的第一个节点的指针

3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出双向链表，程序会根据你的返回值自动打印输出

示例：

思路：

利用中序遍历更改节点的指向

代码：

1. class Solution {
2. public:
3. void _Convert(TreeNode*&prev,TreeNode*cur)
4.  {
5.    if(cur==nullptr)
6.    return ;
7. 
8.    _Convert(prev,cur->left);
9.    //root
10.       cur->left=prev;
11.       if(prev)
12.         prev->right=cur;
13.       prev=cur;
14. 
15.     _Convert(prev,cur->right);
16.   } 
17. 
18. TreeNode* Convert(TreeNode* pRootOfTree) {
19.         TreeNode*prev=nullptr;
20.     TreeNode*cur=pRootOfTree;
21. 
22.     _Convert(prev,cur);
23.     TreeNode*head=pRootOfTree;
24.     while(head&&head->left)
25.     {
26.       head=head->left;
27.     }
28.     return head;
29.     }
30. };

【LeetCode】236. 二叉树的最近公共祖先、 JZ36 二叉搜索树与双向链表

236. 二叉树的最近公共祖先

JZ36 二叉搜索树与双向链表

热门文章

最新文章

相关电子书