【LeetCode热题】通过任意两种遍历序列构造二叉树【附代码，超详细，建议收藏】

ゝ一世哀愁。 2022-09-10 04:28 140阅读 0赞

### 任意两种遍历序列构造二叉树 ###

*  前言
 *  一、从中序与后序遍历序列构造二叉树
 *  二、 从前序与中序遍历序列构造二叉树
 *  三、根据前序和后序遍历构造二叉树
 *  总结

猜你喜欢：  
[【算法入门】最短时间学会DFS深度优先搜索][DFS]

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

# 前言 #

首先来回忆一下三种遍历方式，前序遍历：根左右。中序遍历：左根右。后序遍历：左右根。

【建议收藏】

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

# 一、从中序与后序遍历序列构造二叉树 #

首先说明，这三道题万变不离其中，我们在这里都用递归的方式去求解，我个人认为这道题比较典型，我们在这里就先讲述这题  
[从中序与后序遍历序列构造二叉树][Link 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16]  
题目很短，要如何做呢，如果我们先不用代码做，我们通过画图的方式先理解一下例如，给出

中序遍历 inorder = \[9,3,15,20,7\]  
后序遍历 postorder = \[9,15,7,20,3\]  
![在这里插入图片描述][f812ce8da3be45658c8d2630369f9c1e.png]  
分析：  
我们首先找比较好确定的，这颗树的根肯定是很明显的了，后序遍历的最后一个（postend），这个肯定是跑不了了，那我们我们有了根，只需要去递归构建根的左子树和右子树了，那么应该怎么做呢？  
答案：我们通过遍历中序区间就可以找到**左子树的区间和右子树的区间！**  
这句话非常重要！！！我们能从左子树拿到左子树的中序区间，想要构建左子树也是不够的，不信你自己拿着左区间弄一个左子树试试，那我们这里有了左子树的区间，我们同时知道**后序遍历实现递归构建左子树的**，那么我们这里就等于找到了**中序遍历和后序遍历的左子树区间**！！！！  
看到这里有没有感觉到我们将问题给子问题，那么拿着中序遍历和后序遍历的左子树区间又要怎么做呢？我们是不是看看能否继续拆分子区间，然后等到区间只有一个值的时候说明他已经走到中序区间的最左端了，相当于你走中序遍历的时候走到 **“南墙”** 了，如图：当中序遍历和后序遍历的左区间只有一个值时，不可以再拆分了，此时他就是一个转折点。  
**root为当前区间的根！**  
**root为当前区间的根！**  
**root为当前区间的根！**（左区间也好，右区间也一样！！）  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution { 
    public:
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder, int ini, int inend, int posti, int postend)
    { 
    	//当区间中存在一个值的情况都需要进来，当不存在的时候直接返回
        if (ini > inend || posti > postend)
            return NULL;
            
            //用后序遍历的最后一个元素（根）创造头结点
            //每次进来创建头结点，链接左子树和右子树，注意这里的root就是当前区间的根
        TreeNode* root = new TreeNode(postorder[postend]);
        
    	//对区间至少为2的才考虑
        if (ini + 1 <= inend)
        { 
         //[ini,index-1]index[index+1,inend]中序区间
         //[posti,posti+cut][posti+cut+1,postend-1]postend后序区间
            int index = ini;
            while (inorder[index] != postorder[postend])
            { 
                index++;
            }
            //左子树的节点数
            int cut = index - ini ;
    
            root->left = _buildTree(inorder, postorder, ini, index - 1, posti, posti + cut-1 );
    
            root->right = _buildTree(inorder, postorder, index+1, inend, posti + cut, postend - 1);
    
           
        }
    	//区间为一的情况或者最后返回都是返回当前创造的节点
        return root;
    
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { 
        return _buildTree(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1);
    }
    };

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

# 二、 从前序与中序遍历序列构造二叉树 #

[从前序与中序遍历序列构造二叉树][Link 2]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
倘若上道题没有听懂也无妨，这道题对于上题懂了的同学实际是更加方便解决的。  
分析：前序遍历和中序遍历，我们同样可以将两种遍历分别区分左区间和右区间，然后再通过这两个区间再递归往下走。实际上就这样就可以了  
当然我这里甚至可以用一个prei（前序遍历的指针）走就可以，因为我们每次刚好拿到的都是根，就不用向上题那样确定两个遍历序列的区间在去找根。

class Solution { 
    public:
        TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,
            int& prei, int ini, int inend)
        { 
            //拿preorder[prei]来建根
            TreeNode* root = new TreeNode(preorder[prei]);
    
            int index = ini;
            while (preorder[prei] != inorder[index])
            { 
                index++;
            }
            //中序[ini,index-1]index[index+1,inend]
            if (ini <= index - 1)
            { 
                //表示左区间存在
                root->left = _buildTree(preorder, inorder, ++prei , ini, index - 1);
            }
            else
                root->left = NULL;
    		
    		//表示右区间存在
            if (index + 1 <= inend)
            { 
                root->right = _buildTree(preorder, inorder, ++prei, index + 1, inend);
            }
            else
                root->right = NULL;
    		//最后返回根
            return root;
        }
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 
            int i = 0;
            return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
        }
    };

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

# 三、根据前序和后序遍历构造二叉树 #

[根据前序和后序遍历构造二叉树][Link 3]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
首先这题说明一下，这道题是有多种答案的，我们只需要返回其中一种。  
我们的解法也是和上题一样，找到前序遍历和后序遍历的左区间和右区间，然后递归构建左子树和右子树。

**大家可以尝试自己写一写，再对一下下面的答案！！**

class Solution { 
    public:
        TreeNode* _constructFromPrePost(vector<int>& preorder, vector<int>& postorder,
            int prei, int preend, int posti, int postend)
        { 
            //相等的时候说明都还有一个节点可以创建
            if (prei > preend || posti > postend)
                return NULL;
            int val = preorder[prei];
            TreeNode* root = new TreeNode(val);
    
            //记录左子树的节点个数
            int postbegin = posti;
            //当后序遍历的头尾指向不是同一个的时候说明还可以进行拆分
            if (posti+1<=postend)
            { 
                while (postbegin <= postend)
                { 
                    if (postorder[postbegin] == preorder[prei + 1])
                    { 
                        break;
                    }
                    else
                        postbegin++;
                }
                int cut = postbegin - posti + 1;//左子树的节点个数
            //划分区间
            //左区间[prei+1,prei+cut] [posti, posti+cut-1]
            //右区间 [previ+cut+1,preeend] [posti+cut,postend-1] 
                root->left = _constructFromPrePost(preorder, postorder, prei + 1, prei + cut, posti, posti + cut - 1);
                root->right = _constructFromPrePost(preorder, postorder, prei + cut + 1, preend, posti + cut, postend - 1);
            }
            //走到这里说明区间只有一个节点，直接返回给上层即可
            //只有一个节点就直接返回节点
            return root;
        }
        TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) { 
            return  _constructFromPrePost(preorder, postorder, 0, preorder.size() - 1, 0, postorder.size() - 1);
        }
    };

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

# 总结 #

任意两种遍历序列构造二叉树的写法这章只写了用递归逻辑去完成，实际上也有用迭代的一些比较巧的方法，大家感兴趣也可以了解了解！！  
看到这里不妨给个一键三连！！

[DFS]: https://blog.csdn.net/weixin_52344401/article/details/119811167?spm=1001.2014.3001.5501
[Link 1]: https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/725a141662c14a32a0c64c26f172bd9f.png
[f812ce8da3be45658c8d2630369f9c1e.png]: /images/20220829/e83d3e668c444de087568c7f7c6b18bf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/4a377e47f1c74ea59bc1de81b7c8e968.png
[Link 2]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/9722e89dad1f432cbcfe5a7bbae46d8a.png
[Link 3]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAXmpoYW9e_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/2aa4c601e8a94e289e949eac0c4c947c.png