CD71.【C++ Dev】二叉树练习题3 (从前序与中序遍历序列构造二叉树、从中序与后序遍历序列构造二叉树)

原创已于 2025-10-11 10:15:30 修改 · 1k 阅读

18 ·

CC 4.0 BY-SA版权

文章标签：

#c++ #开发语言

于 2025-08-23 09:12:07 首次发布

LeetCode题解同时被 3 个专栏收录

77 篇文章

订阅专栏

C++ Develop

74 篇文章

订阅专栏

树

10 篇文章

订阅专栏

1.知识回顾

利用遍历顺序构造二叉树:CE14.【C++ Cont】练习题组15(二叉树专题) [NOIP 2001 普及组] 求先序排列

2.从前序与中序遍历序列构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

分析

由于和CE14.【C++ Cont】练习题组15(二叉树专题)的[NOIP 2001 普及组] 求先序排列题类似,这里简单分析:

前序遍历: 根→左子树→右子树

中序遍历: 左子树→根→右子树

前序遍历最开始出现的就是根,拿到根后去后序遍历中划分左子树和右子树的区间

结论:前序确定根,中序确定左右子树区间

例如LeetCode的测试用例,见下图:

即[9],[3],[15,20,7],再向preorder后看到20,说明3的右子树的根节点是20(可以继续细分,代码中需要递归),.....(代码中可以设置一个指针prev_i来遍历preorder)

需要设置begin和end来标记inorder中需要递归的区间:

注意控制prev_i不能越界

可以得出二叉树的样子:

如果只给了preorder = [3,9,20,15,7],那么单凭前序遍历是不能断定9是左子树的根的,有可能左子树是空树,可能像这样:

代码

class Solution {
public:
    TreeNode* recursive_construct(vector<int>& preorder, vector<int>& inorder, int begin, int end)
    {
        if (begin > end)//如果区间不存在就返回
            return nullptr;
        TreeNode* newnode = new TreeNode(preorder[pre_i]);
        //先获取到preorder[pre_i]在inorder的下标,在[begin,end]中找根
        int root_i = begin;
        for (; root_i <= end; root_i++)
        {
            if (preorder[pre_i] == inorder[root_i])
                break;
        }
        //由于要执行preorder[pre_i] == inorder[root_i]判断,因此pre_i必须在判断结束后++
        pre_i++;
        //划分区间: [begin,root_i-1],[root_i],[root_i+1,end]
        //各自递归,前提:区间是存在的
        newnode->left = recursive_construct(preorder, inorder, begin, root_i - 1);
        newnode->right = recursive_construct(preorder, inorder, root_i + 1, end);
        return newnode;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
    {
        TreeNode* root = recursive_construct(preorder, inorder, 0, inorder.size() - 1);
        return root;
    }
private:
    int pre_i = 0;
};

注意到没有判断pre_i是否越界,因为pre_i一定不可能越界

recursive_construct每调用一次,就创建一个新节点,pre_i就++,

那么recursive_construct调用的次数==节点的数目==pre_i的值,当buildTree函数的root得到值后,pre_i的值为preorder.size(),虽然越界,但recursive_construct函数不再执行

提交结果

3.从中序与后序遍历序列构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由不同的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

分析

和从前序与中序遍历序列构造二叉树思路类似

中序遍历: 左子树→根→右子树

后序遍历: 左子树→右子树→根

后序遍历的最后元素一定是根,那么有以下结论

结论:后序确定根,中序确定左右子树区间

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* recursive_construct(vector<int>& inorder, vector<int>& postorder, int begin, int end)
    {
        if (begin > end)
            return nullptr;
        TreeNode* newnode = new TreeNode(postorder[post_i]);
        int root_i = begin;
        for (; root_i <= end; root_i++)
        {
            if (postorder[post_i] == inorder[root_i])
                break;
        }
        post_i--;
        newnode->right = recursive_construct(inorder, postorder, root_i + 1, end);
        newnode->left = recursive_construct(inorder, postorder, begin, root_i - 1);
        return newnode;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
    {
        post_i = postorder.size() - 1;
        //后序确定根,中序确定左右子树区间
        TreeNode* root = recursive_construct(inorder, postorder, 0, inorder.size() - 1);
        return root;
    }
private:
    int post_i;
};

post_i从后往前遍历postorder

★细节提醒

先递归右子树再递归左子树,这里和从前序与中序遍历序列构造二叉树题的代码不同

newnode->right = recursive_construct(inorder, postorder, root_i + 1, end);
newnode->left = recursive_construct(inorder, postorder, begin, root_i - 1);