105. 从前序与中序遍历序列构造二叉树


105. 从前序与中序遍历序列构造二叉树

难度中等 719
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
    3
   /
  9  20
    /  
   15   7

    HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) &#123;
        for(int i=0;i<inorder.length;i++)&#123;
            map.put(inorder[i],i);
        &#125;
        return helper(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    &#125;
    public TreeNode helper(int[] preorder, int[] inorder,int pstart,int pend,int start,int end)&#123;
        if(pstart>pend)&#123;
            return null;
        &#125;// 必须有
        TreeNode root = new TreeNode(preorder[pstart]);
        int idxroot = map.get(preorder[pstart]);
        int leftSize= idxroot - start;//
        root.left = helper(preorder,inorder,pstart+1,pstart+leftSize,start,idxroot-1);
        root.right= helper(preorder,inorder,pstart+leftSize+1,pend,idxroot+1,end);//+1
        return root;
    &#125;

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
104. 二叉树的最大深度 104. 二叉树的最大深度
104. 二叉树的最大深度难度简单 722给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例:给定二叉树 [3,9,20,null,null,15,7],   
2020-10-23 future
下一篇 
206. 反转链表 206. 反转链表
206. 反转链表难度简单 1288反转一个单链表。示例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL进阶:你可以迭代或递归地反转链
2020-10-20 future
  目录