106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 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
保证是树的后序遍历
题解
为了根据中序遍历(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>& inorder, vector<int>& postorder) {
return buildTreeHelper(inorder, 0, inorder.size(), postorder, 0, postorder.size());
}
TreeNode* buildTreeHelper(vector<int>& inorder, int i_start, int i_end, vector<int>& 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;
}
};
问:left_num是干什么的?
答:在提供的代码中,left_num
用于计算中序遍历数组 inorder
中根节点左侧的元素数量,即左子树的节点数量。这个值非常关键,因为它帮助我们在递归过程中正确地划分中序和后序遍历数组,从而构造出正确的左子树和右子树。
-
划分中序遍历数组:在中序遍历数组
inorder
中,根节点左侧的所有元素都属于左子树,右侧的所有元素属于右子树。left_num
指示了左子树元素的数量,因此我们可以使用left_num
将中序遍历数组分为左右两部分。 -
划分后序遍历数组:在后序遍历数组
postorder
中,前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_start
到i_root_index
的部分,postorder
数组中从p_start
到p_start + left_num
的部分。 - 右子树:
inorder
数组中从i_root_index + 1
到i_end
的部分,postorder
数组中从p_start + left_num
到p_end - 1
的部分。
通过这种方式,我们可以确保在每一步的递归调用中都正确地构造出左右子树。
原文地址:https://blog.csdn.net/gulugulu1103/article/details/134626363
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_12409.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!