600币悬赏解释：从前序与中序遍历序列构造二叉树（java）
各位牛油们好，需要大家的帮助，有偿~
我在刷力扣题目时，遇到一道题很费解：从前序与中序遍历序列构造二叉树
原题的题目链接如下：
一、正确的代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int[]tempPre;
HashMap<Integer,Integer> in_map =new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length!=inorder.length||preorder.length==0)return null;
tempPre=preorder;
for (int i = 0; i < inorder.length; i++) {
in_map.put(inorder[i],i);//这里是保存的中序遍历顺序
}
TreeNode root=helper(0,preorder.length,0,inorder.length);//这里是左闭右开的！
return root;
}
private TreeNode helper(int preStart, int preEnd, int inStart, int inEnd) {
if (preEnd==preStart)return null;
TreeNode node=new TreeNode(tempPre[preStart]);//获取头结点
int rootIndex_Inorder= in_map.get(node.val);//头结点在中序遍历中的序号
int leftNum=rootIndex_Inorder-inStart;//左子树的节点数量
node.left=helper(preStart+1,(preStart +1)+ leftNum,
inStart,rootIndex_Inorder);
node.right=helper((preStart +1)+leftNum,preEnd,
rootIndex_Inorder+1,inEnd);
//我的错误疑问代码地方↓
/* node.left=helper(preStart+1,rootIndex_Inorder+1,
inStart,rootIndex_Inorder); node.right=helper(rootIndex_Inorder+1,preEnd,
rootIndex_Inorder+1,inEnd);*/
return node;
}
} 二、我的疑问
画图范围应该如下所示（图是从正确答案的解析处下载下来改过的名称的）
在进入下一层递归时，左子树范围：
在进入下一层递归时，右子树范围：
那么，图中是不是有如下关系成立呢？
////下面是前序遍历的索引范围 //A前序遍历的左子树索引范围：[p_start+1,root_Index_Inorder+1) p_startA=p_start+1 p_endA=root_Index_Inorder+1 //B前序遍历的右子树索引范围：[root_Index_Inorder+1,p_end) p_startB=root_Index_Inorder+1 p_endB=p_end ////////////////////////////////////// ////下面是中序遍历的索引范围 ///////////////////////////////////// //A中序遍历的左子树范围：[i_start,root_Index_Inorder) i_startA=i_start i_endA=root_Index_Inorder ///B中序遍历的右子树范围：[root_Index_Inorder+1,i_end) i_startB=root_Index_Inorder+1 i_endB=i_end
如果以上关系成立，那为什么把递归改成下面的就是错的？（变量名称变化了）
private TreeNode helper(int preStart, int preEnd, int inStart, int inEnd) {
if (preEnd==preStart)return null;
TreeNode node=new TreeNode(tempPre[preStart]);//获取头结点
int rootIndex_Inorder= in_map.get(node.val);//头结点在中序遍历中的序号
int leftNum=rootIndex_Inorder-inStart;//左子树的节点数量
/*node.left=helper(preStart+1,(preStart +1)+ leftNum,
inStart,rootIndex_Inorder);
node.right=helper((preStart +1)+leftNum,preEnd,
rootIndex_Inorder+1,inEnd);*/
node.left=helper(preStart+1,rootIndex_Inorder+1,
inStart,rootIndex_Inorder);//我的错误疑问代码地方
node.right=helper(rootIndex_Inorder+1,preEnd,
rootIndex_Inorder+1,inEnd);//我的错误疑问代码地方
return node;
} 恳请各位牛油赐教，谢谢~
投递京东等公司10个岗位
海康威视公司福利 1125人发布