当前位置：首页 > article >正文

力扣二叉树--第三十三天

article 2024/11/18 23:28:22

前言

前面都是遍历，今天是构造二叉树。

前序和中序可以唯一确定一棵二叉树。

后序和中序可以唯一确定一棵二叉树。

前序和后序不能唯一确定一棵二叉树！

内容

一、从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

递归

用哈希表存储中序序列

后序遍历的末尾元素为当前子树的根节点，找出它在中序遍历中的位置，以此来分割

func buildTree(inorder []int, postorder []int) *TreeNode {
    hashMap:=map[int]int{}
    for i,v:=range inorder{
        hashMap[v]=i
    }
    var build func(int,int)*TreeNode
    build=func(inorderLeft,inordeRight int)*TreeNode{
        if inorderLeft>inordeRight{
            return nil
        }
        val:=postorder[len(postorder)-1]
        postorder=postorder[:len(postorder)-1]
        root:=&TreeNode{Val:val}
          // 由于我们每次都从后序遍历的末尾取元素，所以要先遍历右子树再遍历左子树
      inorderRoot:=hashMap[val]
      root.Right=build(inorderRoot+1,inordeRight)
      root.Left=build(inorderLeft,inorderRoot-1)
      return root
    }
    return build(0,len(inorder)-1)
}

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

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

递归

此时，前序遍历的首元素为当前子树的根节点，找出它在中序遍历中的位置，以此来分割

别忘了要更新前序遍历，将用过的首元素去掉

func buildTree(preorder []int, inorder []int) *TreeNode {
    hashMap:=map[int]int{}
    for i,v:=range inorder{
        hashMap[v]=i
    }
    var build func(int,int)*TreeNode
    build=func(inorderLeft,inorderRight int)*TreeNode{
         if inorderLeft>inorderRight{
             return nil
         }
        
           val:=preorder[0]
        root:=&TreeNode{Val:val}
        preorder=preorder[1:]//少了这一步
        inorderRoot:=hashMap[val]
        root.Left=build(inorderLeft,inorderRoot-1)
        root.Right=build(inorderRoot+1,inorderRight)
        return root
    }
  return build(0,len(inorder)-1)
}

func buildTree(preorder []int,inorder []int)*TreeNode{
    if len(preorder)==0{
        return nil
    }
    root:=&TreeNode{preorder[0],nil,nil}
    i:=0
    for ;i<len(inorder);i++{
        if inorder[i]==preorder[0]{
            break
        }
    }
    root.Left=buildTree(preorder[1:len(inorder[:i])+1],inorder[:i])
    root.Right=buildTree(preorder[len(inorder[:i])+1:],inorder[i+1:])
    return root
}