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

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

三月 14, 2020

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

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

  3
 / \
9  20
  /  \
 15   7

先看这么一颗树:

         1
   /        \
  2         3
 / \        / \
4   5     6   7
         /  \
        8    9

前序遍历为: [1,2,4,5,3,6,8,9,7]
中序遍历为: [4,2,5,1,8,6,9,3,7]
这棵树的根节点为 1,能够由前序遍历的第一个元素知道.
然后看中序遍历, 1 的左边,为左子树,1 的右边为右子树.以左子树 4,2,5 为例.
在前序遍历中,2,4,5和3,6,8,9,7分别为1的左右子树 . 遍历2,4,5第一个遍历到的是2,说明2为这棵树的根节点,然后再去中序遍历找,这么递归下去.
[1,==2,4,5==,==3,6,8,9,7==]
[==4,2,5==,1,==8,6,9,3,7==]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0)return null;
        return build(preorder,inorder,0,inorder.length-1,0);
    }
    public TreeNode build(int[]preorder,int[]inorder,int is,int ie,int now){
    //is和ie,表示inorder中的起始位置和结束位置,也就是这棵树的范围,now表示preorder中的根节点位置.
        if(is>ie||is<0||ie>inorder.length)return null;//这个范围是我测试很多组数据试出来的
        TreeNode node=new TreeNode(preorder[now]);
        if(is==ie)return node;
        int i=is;
        for(i=is;i<ie;i++){//在inorder内查找根节点的位置
            if(preorder[now]==inorder[i])break;
        }
        //对于前序遍历来说,左子树的根节点是now+1,比如上面的preorder1后面是2
        //右子树的根节点需要用now再加上左子树的节点数量
        node.left=build(preorder,inorder,is,i-1,now+1);
        node.right=build(preorder,inorder,i+1,ie,now+i-is+1);
        return node;
    }
}

leetcode 47/100