本文介绍: 给定两个整数数组inorderpostorder,其中inorder二叉树的中序遍历postorder是同一棵树的后序遍历,请你构造返回这颗二叉树。**输入:**inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]**输入:**inorder = [-1], postorder = [-1][-1]postorderpostorderinorderinorderpostorder

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

labuladong 题解思路

给定两个整数数组 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]

提示:

题解

为了根据中序遍历inorder)和后序遍历postorder)重建二叉树我们可以利用中序和后序遍历的特性

重建的基本思路是使用后序遍历的最后一个元素确定根节点然后根据这个根节点将中序遍历分割为左右子树。接着对左右子树递归地进行同样的操作

以下是 C++ 中的实现

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int&gt;&amp; inorder, vector<int&gt;&amp; postorder) {
        return buildTreeHelper(inorder, 0, inorder.size(), postorder, 0, postorder.size());
    }

    TreeNode* buildTreeHelper(vector<int&gt;&amp; inorder, int i_start, int i_end, vector<int&gt;&amp; postorder, int p_start, int p_end) {
        if (p_start == p_end) {
            return nullptr;
        }
        int root_val = postorder[p_end - 1];
        TreeNode* root = new TreeNode(root_val);

        int i_root_index = 0;
        for (int i = i_start; i < i_end; i++) {
            if (inorder[i] == root_val) {
                i_root_index = i;
                break;
            }
        }

        int left_num = i_root_index - i_start;
        root->left = buildTreeHelper(inorder, i_start, i_root_index, postorder, p_start, p_start + left_num);
        root->right = buildTreeHelper(inorder, i_root_index + 1, i_end, postorder, p_start + left_num, p_end - 1);
        
        return root;
    }
};

算法说明

  1. postorder取出最后一个元素,这是当前的根节点

  2. inorder 中找到这个根节点的位置,这将中序遍历分割为左右子树。

  3. 对左右子树递归执行上述过程

  4. 构建当前的根节点,并将其左右子树分别设置为递归调用返回结果

  5. 返回构建的树的根节点。

问:left_num是干什么的?
答:在提供的代码中,left_num 用于计算中序遍历数组 inorder 中根节点左侧的元素数量,即左子树的节点数量。这个值非常关键,因为它帮助我们在递归过程正确划分中序和后序遍历数组,从而构造正确左子树和右子树。

具体来说,left_num 的作用如下:

  1. 划分中序遍历数组:在中序遍历数组 inorder 中,根节点左侧的所有元素都属于左子树,右侧的所有元素属于右子树。left_num 指示了左子树元素的数量,因此我们可以使用 left_num 将中序遍历数组分为左右两部分。

  2. 划分后序遍历数组:在后序遍历数组 postorder 中,前 left_num 个元素对应左子树的后序遍历,其余元素(除了最后一个元素,即当前的根节点)对应于右子树的后序遍历。

下面是如何使用 left_num 划分这两个数组的示例

int left_num = i_root_index - i_start;
root->left = buildTreeHelper(inorder, i_start, i_root_index, postorder, p_start, p_start + left_num);
root->right = buildTreeHelper(inorder, i_root_index + 1, i_end, postorder, p_start + left_num, p_end - 1);

在这段代码中,buildTreeHelper 函数两次调用一次用于构建左子树,一次用于构建右子树:

  • 左子树:inorder 数组中从 i_starti_root_index 的部分,postorder 数组中从 p_startp_start + left_num 的部分。
  • 右子树:inorder 数组中从 i_root_index + 1i_end 的部分,postorder 数组中从 p_start + left_nump_end - 1 的部分。

通过这种方式我们可以确保在每一步的递归调用中都正确构造出左右子树。

原文地址:https://blog.csdn.net/gulugulu1103/article/details/134626363

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_12409.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注