博客

题目

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

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

3

/

9 20

/

15 7

思路

【根 左子树 右子树】

【左子树 根 右子树】

只要中序遍历定位到根节点，就知道左右子树的节点数目，然后递归继续求左右子树的根节点。

中序遍历的定位可以用哈希表快速实现。

代码

 public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
  //将中序遍历的数值映射到哈希表中，<值，出现位置>
  private Map<Integer,Integer> map;
  public TreeNode buildTree(int[] preorder, int[] inorder) {
      int n = preorder.length;
      map = new HashMap<>();
      for(int i = 0;i<n;i++){
          map.put(inorder[i],i);
      }
      return myBuildTree(preorder,inorder,0,n-1,0,n-1);
  }
  //变量不用全部另外初始化也行
 public TreeNode builder(int [] preorder,int pre_left,int pre_right,int []inorder,int in_left,int in_right){
        if (pre_left > pre_right) {
            return null;
        }
        //int pre_root = pre_left;
        //中序遍历中根节点的位置
        int in_root = map.get(preorder[pre_left]);
        // 根节点
        TreeNode root = new TreeNode(preorder[pre_left]);
        // 左子树长度
        int size_left = in_root-in_left;
        //左孩子
        root.left = builder(preorder,pre_left+1,pre_left+size_left,inorder,in_left,in_left+size_left);
        // 右孩子
        root.right = builder(preorder,pre_left+size_left+1,pre_right,inorder,in_root+1,in_right);
        return root;
    }

  public TreeNode myBuildTree(int[] preorder, int[] inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){
      //叶子节点的情况，size_left为0，那么preorder_root+1就会大于preorder_root+size_left
      if (preorder_left > preorder_right) {
          return null;
      }
      int preorder_root = preorder_left;
      int inorder_root = map.get(preorder[preorder_root]);
      //建立根节点
      TreeNode root = new TreeNode(preorder[preorder_root]);
      int size_left = inorder_root-inorder_left;//得到左子树的节点数目
      root.left = myBuildTree(preorder,inorder,preorder_root+1,preorder_root+size_left,inorder_left,inorder_root-1);
      root.right = myBuildTree(preorder,inorder,preorder_root+size_left+1,preorder_right,inorder_root+1,inorder_right);
      return root;

  }