首页 > 300币悬赏解释:从前序与中序遍历序列构造二叉树(java)
头像
牛小弟
编辑于 2020-05-31 11:30
+ 关注

300币悬赏解释:从前序与中序遍历序列构造二叉树(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);//这里是左闭右开的!
        //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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐