各位牛油们好,需要大家的帮助,有偿~
我在刷力扣题目时,遇到一道题很费解:从前序与中序遍历序列构造二叉树
原题的题目链接如下:
一、正确的代码如下:
/** * 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);//这里是左闭右开的! //TreeNode root=helper(0,preorder.length-1,0,inorder.length-1);//这里犯了大错!!! 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; }
恳请各位牛油赐教,谢谢~
全部评论
(0) 回帖