作者：小卢
专栏：《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. };
