在力扣106题
中序遍历和后续遍历推树的问题中
以下是我通过的代码，但是
cout<<zz<<" "<<zy<<" "<<hz<<" "<<hy<<endl;此句不能省略，如果省略就会结果异常，苦思许久不得其解，求一大神解惑，
为什么这条本不影响结果的语句省略会出现结果异常？
/**
* 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* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n=inorder.size();
int zz=0,zy=n-1;
int hz=0,hy=n-1;
return dfs(inorder,postorder,zz,zy,hz,hy);
}
TreeNode* dfs(vector<int>& inorder,vector<int>& postorder,int zz,int zy,int hz,int hy)
{
cout<<zz<<" "<<zy<<" "<<hz<<" "<<hy<<endl;//此句省略会异常
if(zz==zy)//中序，左界=右界
{
TreeNode* root=new TreeNode(0);//新建节点
root->val=postorder[hy];//根值为后序右1
return root;
}
if(hz>hy){//后续左界大于右界
return nullptr;
}
if(zz>zy){//中序左界大于右界
return nullptr;
}
TreeNode* root=new TreeNode(0);
root->val=postorder[hy];
int t;//记录根下标
for(int i=zz;i<zy;i++)
{
if(inorder[i]==postorder[hy])
t=i;
}
root->left=dfs(inorder,postorder,zz,t-1,hz,hz+t-zz-1);//递归求左
root->right=dfs(inorder,postorder,t+1,zy,hz+t-zz,hy-1);//递归求右
return root;
}
};
你的main函数发一下，我这边测试是没有问题的
LeetCode 106 题是关于构建二叉树的题目，题目要求根据给定的中序遍历和后序遍历结果构造出对应的二叉树。
以下是一个基于 C++ 的实现示例：
#include <vector>
#include <unordered_map>
using namespace std;
// 定义二叉树结点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder,
unordered_map<int, int>& indexMap,
int inStart, int inEnd, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return nullptr;
}
// 后序遍历的最后一个元素为根节点
int rootVal = postorder[postEnd];
TreeNode* root = new TreeNode(rootVal);
// 在中序遍历数组中找到根节点的位置
int rootIndex = indexMap[rootVal];
// 根据根节点将中序遍历数组划分为左子树和右子树
int leftSize = rootIndex - inStart;
// 递归构建左子树和右子树
root->left = buildTreeHelper(inorder, postorder, indexMap,
inStart, rootIndex - 1,
postStart, postStart + leftSize - 1);
root->right = buildTreeHelper(inorder, postorder, indexMap,
rootIndex + 1, inEnd,
postStart + leftSize, postEnd - 1);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n = inorder.size();
if (n == 0 || postorder.size() != n) {
return nullptr;
}
// 使用哈希表存储中序遍历数组的每个元素和对应的索引
unordered_map<int, int> indexMap;
for (int i = 0; i < n; i++) {
indexMap[inorder[i]] = i;
}
return buildTreeHelper(inorder, postorder, indexMap, 0, n - 1, 0, n - 1);
}
在上面的代码中，buildTree 函数是主函数，它接收中序遍历和后序遍历结果的数组作为输入，并返回构建好的二叉树的根节点。
buildTreeHelper 函数是一个辅助函数，用于递归构建二叉树。它接收中序遍历和后序遍历结果的数组、中序遍历数组中每个元素及其对应的索引的哈希表、以及当前处理的子数组的起始和终止位置作为输入。
在 buildTreeHelper 函数中，首先判断递归结束的条件。如果中序遍历数组为空或者后序遍历数组为空，说明当前子树为空，返回 nullptr。
然后，根据后序遍历数组的最后一个元素创建根节点，并在中序遍历数组中找到根节点的位置。
接下来，根据根节点将中序遍历数组划分为左子树和右子树。根据左子树的大小，可以计算出后序遍历数组中左子树和右子树的范围。
最后，递归调用 buildTreeHelper 函数构建左子树和右子树，并将它们连接到根节点上。
最终，返回构建好的二叉树的根节点。
你可以在测试环境中使用给定的中序遍历和后序遍历数组来验证以上代码是否正确。
【以下回答由 GPT 生成】
这段代码在递归调用dfs函数的时候，传入的参数zz、zy、hz、hy取值范围是根据当前节点的左子树和右子树的中序和后序遍历序列长度来确定的。当递归调用dfs函数的时候，传入的参数是不同的，所以你输出了zz、zy、hz、hy的值是为了调试程序，以便确认传入的参数是正确的。如果你省略了输出语句，就无法观察到传入参数的值，可能导致结果异常。
如果你的意思是说在运行时没有输出语句就会导致错误结果，这可能是因为输出语句本身会导致程序的执行速度变慢，可能会影响程序的执行顺序，从而导致结果的不同。这种情况下，你可以尝试在执行结果正确的情况下，将输出语句去掉，看是否仍然可以得到正确的结果。
【相关推荐】