二叉树构造篇

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

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder)==0 || len(inorder)==0{
        return nil
    }
    index := find(preorder,inorder) //找到分界点
    return &TreeNode{
        Val : preorder[0],
        Left : buildTree(preorder[1:len(inorder[:index])+1],inorder[:index]),
        Right : buildTree(preorder[len(inorder[:index])+1:],inorder[index+1:]),
    }
}

func find(preorder,inorder []int)int{
    for i:=0;i<len(inorder);i++{
        if preorder[0]==inorder[i]{
            return i
        }
    }
    return -1
}

关键代码解释:
第8行:

 Left : buildTree(preorder[1:len(inorder[:index])+1],inorder[:index]),

  • 中序遍历直接从index分,而前序遍历可以根据中序遍历长度推断出来,因为同一个的树前序、中序数量是一样的。
  • 这里加1是因为第一个是根节点,左子树的前序遍历不包括这个所以加1

第9行:

 Right : buildTree(preorder[len(inorder[:index])+1:],inorder[index+1:]),
  • 中序遍历从index分,前序遍历结果是根节点、左子树递归遍历、右子树递归遍历
  • preorder[:len(inorder[:index])+1]是根节点加左子树递归遍历结果
  • 所以右子树前序遍历就是preorder[len(inorder[:index])+1:]

与前序和后序遍历构造二叉树类似,都会用到一个很重的点,就是中序数组大小一定是和后序数组的大小相同的

func buildTree(inorder []int, postorder []int) *TreeNode {
    if len(inorder)==0 || len(postorder)==0{
        return nil
    }
    index := find(inorder,postorder)
    return &TreeNode{
        Val : postorder[len(postorder)-1],
        Left :buildTree(inorder[:index],postorder[:index]),
        // 同一个的树后序、中序数量是一样的
        Right :buildTree(inorder[index+1:],postorder[index:len(postorder)-1]),
    }
}

func find(inorder []int,postorder []int)int{
    for i:=0;i<len(inorder);i++{
        if inorder[i] == postorder[len(postorder)-1]{
            return i
        }
    }
    return -1
}

第9行 Right 这里:

 Right :buildTree(inorder[index+1:],postorder[index:len(postorder)-1]),
  • 首先后序遍历数组postorder最后一个元素不要,它是根节点,还剩下左子树后序遍历数组+右子树后序遍历数组
  • 其次因为中序数组大小一定是和后序数组的大小相同,左子树中序遍历数组为inorder[:index]
  • 所以右子树后序遍历数组为postorder[index:len(postorder)-1])

参考: