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

我不是女神ヾ 2024-03-16 13:41 3阅读 0赞

>  作者：小卢
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![7d63d497b5114103b3dd7633a1ba4731.jpeg][]
> 
> --------------------

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

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

题目描述：

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

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

示例：

![d2722eac9ffc42ae8feb51e1a0cce4e9.png][]

思路：

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

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

代码：

class Solution {
    public:
            bool GetPath(TreeNode*root,TreeNode*x,stack<TreeNode*>&Path)
            {
                if(root==nullptr)
                return false;
                Path.push(root);
                if(x==root)
                return true;
                
                if(GetPath(root->left,x,Path))
                    return true;
                if(GetPath(root->right,x,Path))
                    return true;
                Path.pop();
                return false;
    
            }
    
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            stack<TreeNode*>pPath,qPath;
            GetPath(root,p,pPath);
            GetPath(root,q,qPath);
            while(pPath.size()!=qPath.size())
            {
                if(pPath.size()>qPath.size())
                pPath.pop();
                else
                qPath.pop();
            }
            while(pPath.top()!=qPath.top())
            {
                pPath.pop();
                qPath.pop();
            }
            return pPath.top();
        }
    };

## JZ36 二叉搜索树与双向链表 ##

[二叉搜索树与双向链表\_牛客题霸\_牛客网][Link 1]

题目描述：

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

![d7d47e26364a69bd1295f58ed4e488fd.png][]

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

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继  
2.返回链表中的第一个节点的指针  
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

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

示例：

![7df6f8d9c24f4e1f8836292bb3100651.png][]

思路：

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

代码：

class Solution {
    public:
        void _Convert(TreeNode*&prev,TreeNode*cur)
    	{
    		if(cur==nullptr)
    		return ;
    		
    		_Convert(prev,cur->left);
    		//root
    			cur->left=prev;
    			if(prev)
    		    prev->right=cur;
    			prev=cur;
    		
    		_Convert(prev,cur->right);
    	} 
    
        TreeNode* Convert(TreeNode* pRootOfTree) {
            TreeNode*prev=nullptr;
    		TreeNode*cur=pRootOfTree;
    		
    		_Convert(prev,cur);
    		TreeNode*head=pRootOfTree;
    		while(head&&head->left)
    		{
    			head=head->left;
    		}
    		return head;
        }
    };

[7d63d497b5114103b3dd7633a1ba4731.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/a0f3d78955f44aecb6827340e4501cea.png
[236.]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
[d2722eac9ffc42ae8feb51e1a0cce4e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/dccbd55af54c4da69d1850cde0d8498e.png
[Link 1]: https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking#:~:text=%E4%B8%8B%E4%B8%80%E9%A2%98-,JZ36%20%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%8E%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8,-%E9%A2%98%E7%9B%AE
[d7d47e26364a69bd1295f58ed4e488fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/f88c08c7c0534618b9bc5be318caad05.png
[7df6f8d9c24f4e1f8836292bb3100651.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/901f0f7539c34102bf5f36c33ace5be6.png