树结构是一类重要的非线性数据结构。直观来看，树是以分支关系定义的层次结构。树结构在客观世界广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。
树在计算机领域中也得到广泛应用，尤以二叉树最为常用。如在操作系统中，用树来表示文件目录的组织结构。在编译系统中，用树来表示源程序的语法结构。在数据库系统中，树结构也是信息的重要组织形式之一

对于二叉树的定义以及数据结构，我们就不再赘述，今天主要讲一下如何构造一颗二叉树

二叉树的遍历

查看leetcode关于构造二叉树的题目，发现他们都是基于二叉树的前、中、后序遍历去构造，那么在我们先了解一下二叉树的遍历

首先我们定义一个二叉树的数据结构，这里以Go为例：

1
2
3
4
5
type TreeNode struct {
     Val int
     Left *TreeNode
     Right *TreeNode
}

这里我们引入一个框架，通过框架一次性解决二叉树遍历问题：

1
2
3
4
5
6
7
8
9
10
func traverse(root *TreeNode) {
    if root == nil {
        return nil
    }
    // 前序位置
    traverse(root.Left)
    // 中序位置
    traverse(root.Right)
    // 后序位置
 }

通过以上框架，二叉树的前、中、后序遍历，在对应位置添加对应代码即可，以leetcode114题「二叉树的前序遍历」为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 func preorderTraversal(root *TreeNode) []int {
    var res []int
    var traverse func(*TreeNode)

    traverse = func (node *TreeNode) {
        if node == nil {
            return
        }
        // 前序位置
        res = append(res, node.Val)
        traverse(node.Left)
        // 中序位置
        traverse(node.Right)
        // 后序位置
    }
    traverse(root)
    return res
}

二叉树的构造

通过前序和中序遍历结果构造二叉树

leetcode第105题「从前序与中序遍历序列构造二叉树」

image-20221120160157599

要构造二叉树，首先第一步就是要找出二叉树的根节点，然后递归构造左右子树即可，根据上文所述的二叉树遍历框架，我们可以得到preorder和inorder数组中的元素分布有如下特点:

image-20221120163554895

由上图可知，根节点就是preorder[0]，因为二叉树特性，无论怎么遍历，左右子树个数始终相同，使用跟节点去inoder数组中获取左右子树的个数，将preorder和inoder数组划分为两部分，递归构造左右子树即可

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]) // len(inorder[:i])+1防止越界
    root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])
    return root
}

通过中序与后序遍历序列构造二叉树

leetcode第106题「从中序与后序遍历序列构造二叉树」

image-20221120165018142

类似前序相关思路，先查看他们的特点：

image-20221120165645418

与前序遍历不同的是，原本根节点从preorder[0]变成了postorder最后一个元素，其余部分基本一样没什么变化

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func buildTree106(inorder []int, postorder []int) *TreeNode {
    if len(inorder) == 0 {
        return nil
    }
    root := &TreeNode{postorder[len(postorder)-1], nil, nil}
    i := 0
    for ; i < len(inorder); i++ {
        if inorder[i] == postorder[len(postorder)-1] { // 找到中序遍历根节点
            break
        }
    }

    root.Left = buildTree106(inorder[:i], postorder[:i])
    root.Right = buildTree106(inorder[i+1:], postorder[i:len(postorder)-1])
    return root
}

通过后序和前序遍历结果构造二叉树

leetcode第889题「从中序与后序遍历序列构造二叉树」

这道题与前面两道题有一个本质上的区别：通过前序+中序或者后序+中序都可以确定一个唯一二叉树，但是前序+后序无法确定一颗唯一的二叉树，为什么呢？

前两道题，可以通过前序或者后序遍历结构找到根节点，然后根据中序遍历确定左右子树。这道题你可以确定根节点，但还是无法确切的知道左右子树有那些节点

举个例子，题目输入：

1
preorder = [1,2,3], postorder = [3,2,1]

下面这两棵树都符合条件的，但是他们的结果完全不同：

虽然无法确定唯一的二叉树，但还是可以还原二叉树，整体逻辑与前两图差别不大：

  1. 首先把前序遍历结果的第一个元素
  2. 然后把前序遍历结果的第二个元素作为左子树的根节点的值
  3. 在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树即可
  4. 后序遍历思路以此类推即可
    示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func constructFromPrePost(preorder []int, postorder []int) *TreeNode {
    if len(preorder) == 0 {
        return nil
    }
    root := &TreeNode{preorder[0], nil, nil}
    if len(preorder) == 1 {
        return root
    }
    i := 0
    for ; i < len(postorder); i++ {
        if preorder[1] == postorder[i] { // 以左序遍历为根节点时,在后续节点中找到根节点
            break
        }
    }

    root.Left = constructFromPrePost(preorder[1:len(postorder[:i+1])+1], postorder[:i+1])
    root.Right = constructFromPrePost(preorder[len(postorder[:i+1])+1:], postorder[i+1:len(postorder)-1])
    return root
}