二叉树

二叉树

数据结构

链表

数组

遍历

递归

迭代

前序遍历

前序遍历是中左右，根据栈FILO的特性，节点入栈的顺序就应该是右左中。因此，先将根节点入栈，当栈非空时，先弹出栈顶并访问该节点，该节点对应中；再将非空右节点和非空左节点入栈，下一轮处理的时候，左就变成了中进行处理，被弹出访问，再将右和左入栈。简言之，此处仅仅访问被定义为中的节点，再入栈右节点和左节点，其实这里的中是相对与自身而言的，但是对于父节点来说是左右节点。对于空节点不会被入栈。

这样思考有点陷入思考递归全过程中。。。其实就是先访问中节点，然后将右节点和左节点入栈。因为左节点自身马上就可以成为下一轮的中节点，自然符合了入栈顺序右左中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func preorderTraversal1(root *TreeNode) (vals []int) {
	//定义栈
	var stack []*TreeNode
	//首先将根节点入栈，如果根节点为空直接返回
	if root == nil {
		return
	}
	stack = append(stack, root)
	//当栈非空，先弹出栈并处理中到结果集，然后将非空右和左压入栈
	for len(stack) != 0 {
		//先弹出栈并处理中
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		vals = append(vals, node.Val)//中（处理）
		//将非空右和左压入栈（访问）
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	return
}

上述处理在逻辑处理上更简单易懂，还有一种做法在逻辑上更加复杂，但为后续中序遍历开了先河。

首先不断访问节点并深入左子树直到为空，当节点为空则弹出栈顶，节点转向栈顶元素的右子树继续处理。此处的栈只是为了记录信息便于转向右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//迭代做法：在访问节点的同时处理节点，要注意右节点和左节点都可以是某棵树的根节点
//逻辑上更复杂抽象，同时处理左子树、右子树和栈的操作
//一旦遍历到某个节点，将它压入栈，并继续向左移动。如果左子树为空，则弹出栈顶节点并遍历它的右子树。
func preorderTraversal(root *TreeNode) (vals []int) {
	stack := []*TreeNode{}
	node := root
	for node != nil || len(stack) > 0 {
		//不断访问节点并深入左子树，直到左子树为空
		for node != nil {
			vals = append(vals, node.Val) //访问节点
			stack = append(stack, node)   //入栈仅仅是为了记录和后续回溯访问右子树
			node = node.Left
		}
		//node为空，即左子树为空，要获取右子树，弹出已访问的节点
		node = stack[len(stack)-1].Right //获取右子树
		stack = stack[:len(stack)-1]     //弹出已访问的节点
	}
	return
}

避免非空节点的处理方式，只是用栈来记录非空节点，用来遍历整个树
具体过程：

栈非空时循环：只要栈中还有节点未被处理，继续遍历。

弹出栈顶节点：

使用 stack[len(stack)-1] 获取栈顶节点 node。
更新栈 stack = stack[:len(stack)-1]，移除栈顶元素。
访问当前节点：

将当前节点的值 node.Val 添加到结果切片 vals 中。
压入右子树和左子树：

按照 右子树先压栈、左子树后压栈 的顺序操作。
由于栈是后进先出结构，保证了左子树先被访问（符合前序遍历顺序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func preorderTraversal(root *TreeNode) (vals []int) {
	//定义栈
	var stack []*TreeNode
	//首先将根节点入栈，如果根节点为空直接返回
	if root == nil {
		return
	}
	stack = append(stack, root)
	//当栈非空，先弹出栈并访问中，然后将非空右和左压入栈
	for len(stack) != 0 {
		//先弹出栈并访问中
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		vals = append(vals, node.Val)
		//将非空右和左压入栈
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
	}
	return
}

中序遍历

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：

  1. 处理：将元素放进result数组中
  2. 访问：遍历节点

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

左中右，决定了要先深入到最底下的节点然后从子树往上走。但是不用像左右中考虑节点是否访问过，因为访问左子树能刚好把需要访问的左和中解决了，它能马上获得要访问的右子树。

节点非空则入栈并不断深入左子树，但不访问。节点为空，弹出栈顶并访问，转向处理右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func inorderTraversal(root *TreeNode) (vals []int) {
	stack := []*TreeNode{}
	node := root
	//节点非空或栈非空就遍历所有节点
	for node != nil || len(stack) > 0 {
		//节点非空，一直将节点入栈，并深入左子树
		if node != nil {
			stack = append(stack, node)
			node = node.Left
		} else { //节点为空，弹出栈顶元素并访问，转向右子树进行相同的操作
			node = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			vals = append(vals, node.Val)
			node = node.Right
		}
	}
	return
}

二叉树的后序遍历

后序遍历的顺序是：

  1. 左子树 ->
  2. 右子树 ->
  3. 根节点

这意味着我们会在访问一个节点之前，先处理完它的左子树和右子树。相比前序遍历和中序遍历，后序遍历的实现更复杂，尤其在非递归实现中需要额外判断，以避免错误地重复访问节点。

代码回顾

左右中，左决定了要先深入到最底下的节点然后从子树往上走。访问完左子树后不能马上访问根节点，它要转向右子树进行处理，处理完右子树才能访问根节点，因此需要记录上次访问过的节点，根据记录得知右子树访问完了才能访问根节点。

不断深入左子树但是不访问，节点为空则获取栈顶元素，在访问当前节点之前要做条件判断（当前节点的右子树是否为空或者右子树访问过了），若满足则弹出栈顶元素并访问，标记该节点已经访问过，并将当前节点置为空表明要回溯到父节点，否则转向处理右子树。

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
func postorderTraversal(root *TreeNode) (vals []int) {
    stack := []*TreeNode{}  // 栈用于模拟递归调用
    var prev *TreeNode       // 记录上一个访问的节点
    node := root             // 当前节点

    for node != nil || len(stack) > 0 { // 当节点不为空或栈非空时继续遍历
        if node != nil { 
            // 一直沿着左子树入栈，不访问节点
            stack = append(stack, node)
            node = node.Left
        } else {
            // 如果当前节点为空，说明没有左子树需要处理，节点要回溯到父节点，即尝试获取栈顶节点
            node = stack[len(stack)-1]

            // 对刚回溯到的节点，如果右子树为空或右子树已经访问过，访问当前节点
            if node.Right == nil || node.Right == prev {//记录先前访问过的节点才能确定根节点能不能访问
                stack = stack[:len(stack)-1]  // 弹出栈顶节点
                vals = append(vals, node.Val) // 访问节点
                prev = node                   // 标记当前节点为已访问
                node = nil                    // 设置当前节点为空，准备回溯
            } else {
                // 如果右子树未访问，转向右子树
                node = node.Right
            }
        }
    }
    return
}

算法思路

  1. 用栈模拟递归调用：

    • 在递归实现中，我们先递归处理左子树，然后右子树，最后访问根节点。在非递归实现中，我们使用栈来模拟递归的行为。

  2. 判断右子树是否已经访问：

    • 当弹出一个节点时，我们要判断它的右子树是否已经访问过。如果右子树未访问，我们转向右子树；如果右子树为空或者已访问过，我们才访问当前节点。

  3. 使用 prev 变量：

    • 记录上一个访问过的节点，用于判断是否需要访问当前节点，避免重复访问。

如何处理每种情况

  1. 左子树的遍历：

    • 我们不断将当前节点的左子树入栈，这样可以保证左子树优先处理。

  2. 右子树的判断：

    • 当访问到一个节点时，首先检查右子树是否为空或已经访问过。
      • 如果右子树为空或访问过：我们弹出栈顶节点并访问它。
      • 如果右子树未访问：我们转向右子树继续遍历。

  3. 回溯：

    • 当左右子树都处理完后，我们将当前节点设置为空，表明需要回溯到父节点。

示例：

二叉树结构：

1
2
3
4
5
    1
   / \
  2   3
 / \
4   5
  • 后序遍历结果：[4, 5, 2, 3, 1]

执行过程

  1. 初始状态：stack = []，node = 1

    • 将 1 入栈，继续向左遍历，stack = [1]，node = 2

  2. 将 2 入栈，继续向左遍历，stack = [1, 2]，node = 4

    • 4 没有左子树，将 4 入栈后设置 node = nil

  3. 弹出 4，访问它（因为它没有右子树），vals = [4]

    • 设置 prev = 4，回溯到 2，继续处理右子树

  4. 弹出 5，访问它，vals = [4, 5]，回溯到2

Algorithm
二叉树
http://willxu0313.github.io/2025/04/19/算法题/二叉树/
作者
Will
发布于
2025年4月19日
许可协议