本文对应题目练习：力扣105
内容参考自官方题解

前序和中序性质

以这棵树为例:

1
2
3
4
5
6
7
8
9
        3
       / \
      9  20
     /  /  \
    8  15   7
   / \
  5  10
 /
4

其前序和中序遍历分别为
preorder = [3, 9, 8, 5, 4, 10, 20, 15, 7]
inorder = [4, 5, 8, 10, 9, 3, 15, 20, 7]

以根节点3为例：

  1. 对于前序而言，3一定是第一个元素，后面剩下的元素从某个位置分为左右2个部分，左边均为3的左子孙，右边均为3的右子孙
  2. 对于中序而言，3左边的所有元素均为3的左子孙，右边均为3的右子孙
  3. 按照上述的划分，2个子数组分别作为3的左右子树，递归地满足1和2性质

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

递归法

根据前序遍历的性质，对于某个子树的前序序列，可以直接找到其根节点。
那么很容易想到，可以进一步在中序遍历中划分出当前根节点的左右子树序列，同时根据长度也可以把前序的左右子树序列同样求出；
这样不断划分子树，向下递归，即可逐步重建出整棵树来。

Go语言代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	// 创建当前子树的根节点
	rootVal := preorder[0]
	root := &TreeNode{Val: rootVal}
	// 拆分该根节点的左右子树的遍历序列
	leftInOrder := inorder[:getIndex(inorder, rootVal)]
	rightInOrder := inorder[getIndex(inorder, rootVal)+1:]
	leftPreOrder := preorder[1 : len(leftInOrder)+1]
	rightPreOrder := preorder[len(leftInOrder)+1:]
	// 递归遍历,并进行连接即可
	root.Left = buildTree(leftPreOrder,leftInOrder)
	root.Right = buildTree(rightPreOrder,rightInOrder)
	return root
}

func getIndex(arr []int, val int) int {
	for i, v := range arr {
		if v == val {
			return i
		}
	}
	return -1
}

迭代法

注：本文主要记录了一些细节的逻辑部分，主要的代码思想在官方题解中已经写的很好了。

很巧妙的做法，核心基于前序遍历的一个性质：
对于任意两个连续节点 u 和 v ，其只有2种可能的关系：

  • v 是 u 的左儿子。因为如果u是当前子树的根节点，那么在遍历到 u 之后，下一个遍历的节点就是 u 的左儿子，即 v；
  • u 没有左儿子，并且 v 是 u 的某个祖先节点（或者 u 本身）的右儿子。如果 u 没有左儿子，那么下一个遍历的节点就是 u 的右儿子。如果 u 没有右儿子，就向上不断回溯，直到遇到第一个有右儿子（且 u 不在它的右儿子的子树中）的节点 a ，v 就是 a 的右儿子。

可以根据这棵树来自己思考一下（例如节点4和节点10）：

1
2
3
4
5
6
7
8
9
        3
       / \
      9  20
     /  /  \
    8  15   7
   / \
  5  10
 /
4

根据上面的性质，我们可以直接枚举前序遍历序列，第一个元素必定是根节点。遍历的每一个元素i：

  1. 要么是上一个元素的左孩子；
  2. 要么就是前面某个元素k的右孩子。

对于第一种情况，不断地向左链接即可；
如果遇到了第二种情况，就需要回溯找到这个元素的父亲k，然后将i作为k的右孩子链接即可。

接下来，考虑如何回溯：
考虑到在保持第一种情况下，访问的一系列元素构成一个左斜树，我们用一个栈来记录，当出现了第二种情况时，逐渐弹出栈顶，检验这个栈顶元素是否为满足条件的k，如果是，将i连接为其右孩子即可，然后继续压栈运行。

再接下来，考虑如何发现第二种情况发生：
事实上，栈中的各个元素，从栈顶到栈底，靠栈底元素一定是靠栈顶元素的父亲或祖先。假设一直发生第一种情况，此时中序遍历的序列从左向右的顺序恰好就是栈中从顶到底的序列。
因此，如果我们一直向左子树迭代，到达叶子后就可以进行回溯了，因为接下来必定向（某个）右子树继续迭代，因此必然会出现第二种情况。
这时，我们不断出栈，就能够从栈中找到接下来要迭代的右子树的根节点k，并且在中序遍历序列中，一定会在靠右边（即靠上，即祖先）找到这个元素k（可以考虑一下左斜树的中序遍历），所以，在出栈的时候，不断使用一个指针p右移就可以找到这个元素。

最后，考虑如何检查到达了叶子：
考虑到，既然我们能够从栈中找到k，那么使用指针p来找到k是没有必要的；
但是指针p可以用来标识当前子树的“最靠左”的叶子！只需要让p指向当前子树根节点的右边一个节点即可！
因此，在迭代的时候，只需要检查当前节点是否和中序遍历序列中p指向的节点相等即可，如果相等，说明到达叶子，此时进行回溯即可。

此外，如果是已知中序和后序，那么只需要将上述过程做一个镜像即可。

上面是主要的思路细节，接下来观察代码即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	n := len(preorder)
	rootVal := preorder[0]
	root := &TreeNode{Val: rootVal}
	stack := []*TreeNode{root}
	//cur := root
	for i, j := 1, 0; i < n; i++ {
		cur := stack[len(stack)-1]
		if cur.Val != inorder[j] {
			cur.Left = &TreeNode{Val: preorder[i]}
			stack = append(stack, cur.Left)
		} else {
			for len(stack) != 0 && stack[len(stack)-1].Val == inorder[j] {
				cur = stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				j++
			}
			cur.Right = &TreeNode{Val: preorder[i]}
			stack = append(stack, cur.Right)
		}
	}
	return root
}