【Leetcode】二叉树的最近公共祖先，二叉搜索树转换成排好序的双向链表，前序遍历与中序遍历构造二叉树

Dear 丶 2024-04-22 12:13 36阅读 0赞

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

### 链接 ###

[二叉树的最近公共祖先][Link 1]

### 题目再现 ###

![18db69ae09e946439529be502df7e615.png][]

### 『Ⅰ』思路一：转换成相交链表问题 ###

![3c777bd4dc004a7794d45660fce9d781.png][]

观察上图，节点1和节点4的最近公共祖先是3，这是不是很像相交链表的问题，关于相交链表，曾经我在另一篇文章里写到过，读者可以参考：[反转链表 合并链表 相交链表][Link 2]

但是要转换成相交链表，就要从后向前遍历，如果节点中还存在一个指针，指向父节点就好了，这种结构其实叫三叉链结构：

![d9616d132d3c4ad8b06ffc1d03bb7227.png][]

但是这题给我们的只是一个普通的二叉树，没有三叉链，那该怎么办呢？

那么就转换为第二种思路：寻找节点的祖先路径

### 『Ⅱ』思路二：寻找节点的祖先路径 ###

我们可以把要找的两个节点的路径找出来，然后存到栈里，这样把两个节点的祖先路径找出来后，就可以转换成链表相交问题了。

![e43162eda9e8436a99c3aa714d13d787.png][]

关于该怎么入栈：

我们先让节点入栈，然后判断它是否等于我们要找的节点，如果是，则返回true；如果不是，则

1.如果左节点不为空，返回true；

2.如果右节点不为空，返回true；

3.如果左右节点都为空，则pop掉栈顶的元素，返回false；

完整代码：

class Solution {
    public:
        bool findpath(TreeNode*cur,TreeNode*x,stack<TreeNode*>&path)  //注意这里要传引用
        {
            if(cur==nullptr)
                return false;
            path.push(cur);
            if(cur==x)
                return true;
        
            if(findpath(cur->left,x,path))
                return true;
            if(findpath(cur->right,x,path))
                return true;
    
            path.pop();
            return false;
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
        {
            stack<TreeNode*> ppath;
            stack<TreeNode*> qpath;
            findpath(root,p,ppath);
            findpath(root,q,qpath);
            while(ppath.size()>qpath.size())  //使两个栈一样长
            {
                ppath.pop();
            }
    
            while(ppath.size()<qpath.size())
            {
                qpath.pop();
            }
    
            while(ppath.top()!=qpath.top())   //从栈顶开始，寻找第一个相同的数据
            {
                ppath.pop();
                qpath.pop();
            }
    
            return ppath.top();
        }
    };

![1bdbb39afeed48f399a3fa90b25e0b57.png][]

可以看到，这种方法效率使非常高的，它的时间复杂度是O（N）;

### 『Ⅲ』思路三：暴力查找 ###

其实当两个节点分别在左树和右树时，它们最近的公共祖先就是根节点，如果不在树两边，而是都在左树，或是都在右树，那么就可以转化成子问题，递归解决。

如下图：

![70d921a2be924ee59c5b1f097025a3c2.png][]

注意，如果有一个节点恰好是根节点，那么这个节点就是最近的公共祖先，也是说一个节点的祖先也算它自己。

如下图：

![5061da7068a04a3c9686ba8f05b29cc6.png][]

那么该怎么判断节点是在左树还是右树呢?

我们可以定义四个布尔变量，分别是：pinleft（p在左树） pinright（p在右树）

qinleft （q在左树 ） qinright（q在右树）

哪个布尔值为真就表明这个节点在哪边。

完整代码：

class Solution {
    public:
        bool find(TreeNode*cur,TreeNode*x)
        {
            if(cur==nullptr)
                return false;
            return cur==x||
                   find(cur->left,x)||
                   find(cur->right,x);
        }
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode*q)  
        {
            if(root==nullptr)
                return nullptr;
            if(root==p||root==q)  //某一个节点为根
                return root;
            
            bool pinleft,pinright;
            bool qinleft,qinright;
            pinleft=find(root->left,p);   //去左树寻找p节点
            pinright=!pinleft;
            qinleft=find(root->left,q);   //去左树寻找q节点
            qinright=!qinleft;
            if(pinleft&&qinleft)   //都在左树转化成子问题
                return lowestCommonAncestor(root->left,p,q);
            else if(pinright&&qinright)    //都在右树转化成子问题
                return lowestCommonAncestor(root->right,p,q);
            else    //分别在左树和右树
                return root;
        }
    };

![bcbd91bf27e0456a81a0464c4a84e5d8.png][]

可以看到，这个算法的效率是很差的，它的时间复杂度是O（N^2）。

--------------------

## 二.二叉搜索树转换成排好序的双向链表 ##

### 链接 ###

[二叉搜索树转换成排好序的双向链表][Link 3]

### 题目再现 ###

![da17007e1f3c453ba9bfd0dd89bd5cc7.png][]

### 解法 ###

根据题意，原二叉搜索树的左指针就是双链表的前驱指针，右指针就是双链表的后继指针；

而且本题还要求空间复杂度是O（1），也就是说不能额外开空间，其实要是能额外开空间，那么这题就非常简单了。

我们知道，二叉搜索树的中序遍历结果是升序列，这恰好满足了题目排好序的要求；

那要怎么在原树上操作，使它转换成双链表呢？

举个例子：

对于我们过去（prev）的事，现在（cur）的我们肯定是一清二楚的，而且是可以确定的，但未来（next）的事并不能确定；

但如果我们是从未来穿越回现在的，那么穿越回来的我们，就可以确定未来的事。所以说过去（prev）的未来（next）就是现在（cur）。

回到题目，所以cur的左指针（left）就是双链表的前驱（prev），prev的右指针就是后继（next），然后再更新一下prev即可。

![94218a0854e64401828a41fb8d2d372a.png][]

完整代码：

class Solution {
    public:
    	void InOrder(TreeNode*cur,TreeNode*&prev)   //注意要传引用
    	{
    		if(cur==nullptr)
    			return;
    		
    		InOrder(cur->left,prev);
    		cur->left=prev;   //cur的左指针就是prev
    		if(prev)   //注意判断prev是否为空
    			prev->right=cur;   //prev的右指针就是cur
    		prev=cur;  //更新prev
    		InOrder(cur->right,prev);
    	}
        TreeNode* Convert(TreeNode* pRootOfTree) 
    	{
    		if(pRootOfTree==nullptr)
    			return nullptr;
    		TreeNode*prev=nullptr;   //定义一个前驱指针
    		InOrder(pRootOfTree,prev);   //中序遍历
    		TreeNode*head=pRootOfTree;
    		while(head->left)   //最左边的节点即为双链表的头
    		{
    			head=head->left;
    		}
    
    		return head;
        }
    };

--------------------

## 三.根据一棵树的前序遍历与中序遍历构造二叉树 ##

### 链接 ###

[根据一棵树的前序序列与中序序列构建二叉树][Link 4]

### 题目再现 ###

![28c17505d0714693ab65b45f9ddc74bf.png][]

### 解法 ###

众所周知，前序遍历的顺序为：根 左 右

中序遍历的顺序为：左 根 右

所以根据前序序列就可以确定根，确定了根后就可以分成左子树和右子树；

确定好根后，根据中序序列就可以分割左子树和右子树的区间，然后构建树；

而左子树或是右子树也有根，这样就可以转化成子问题，递归实现，但要注意，前序序列中的每个数只能使用一次。

![a882f5441d1943cda8e493c2f30695d5.png][]

完整代码：

class Solution {
    public:
        //注意这个prei用于遍历前序序列数组，因为每个数只能用一次，所以要传引用
        TreeNode*_build(vector<int>& preorder, vector<int>& inorder,int &prei,int inbegin,int inend)
        {
            if(inbegin>inend)   //当区间不存在时返回空指针
                return nullptr;
           
            TreeNode*preroot=new TreeNode(preorder[prei]);
            int rooti=inbegin;     //找根在中序序列中的位置
            while(rooti<=inend)
            {
                if(preorder[prei]==inorder[rooti])   //找到后跳出循环
                    break;
                rooti++;
            }
            prei++;   //本次确定好根后，prei++找下一个根
            //分割区间，递归构建
            //[inbegin,rooti-1] rooti [rooti+1,inend]
            preroot->left=_build(preorder,inorder,prei,inbegin,rooti-1);
            preroot->right=_build(preorder,inorder,prei,rooti+1,inend);
    
            return preroot;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
        {
            int i=0;
            return _build(preorder,inorder,i,0,inorder.size()-1);
        }
    };

--------------------

> **??本篇文章到此就结束了， 若有错误或是建议的话，欢迎小伙伴们指出；?️?**
> 
> **??希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；??**
> 
> **??谢谢你的阅读。??**

[Link 1]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
[18db69ae09e946439529be502df7e615.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/67881c5b71474c48b969ea9b06e5a7ab.png
[3c777bd4dc004a7794d45660fce9d781.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/d978fd135e304a8994f5ed8a62e066e0.png
[Link 2]: http://t.csdn.cn/t4ejr
[d9616d132d3c4ad8b06ffc1d03bb7227.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/99c6b3b1839a497e9dc696d4598c2e84.png
[e43162eda9e8436a99c3aa714d13d787.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/321dcb05c19f4ec285752ae35b973eb1.png
[1bdbb39afeed48f399a3fa90b25e0b57.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/0ef71627c858466d86df9ddd4258aebf.png
[70d921a2be924ee59c5b1f097025a3c2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/daa05062ea0d4ca890d1fddc0227166f.png
[5061da7068a04a3c9686ba8f05b29cc6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/7ae4ccc4b4254481929235dcc09346d7.png
[bcbd91bf27e0456a81a0464c4a84e5d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/89b2b8b478fb43e69e61c11a80bbf01e.png
[Link 3]: https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13&&tqId=11179&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[da17007e1f3c453ba9bfd0dd89bd5cc7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/4a835731809b40bc939dff7d7761f542.png
[94218a0854e64401828a41fb8d2d372a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/112c329e63a148ada84487772e345b37.png
[Link 4]: https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[28c17505d0714693ab65b45f9ddc74bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/1a8bf020337348bb812492450bed3daf.png
[a882f5441d1943cda8e493c2f30695d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/5d13e67628364208846389753a871d40.png