Fluge Site

二叉树的各种遍历方式,包括递归和非递归的整理

  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
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    //递归解法
    func PreOrderTraversal(root *TreeNode) []int {
    	if root == nil {
    		return nil
    	}
    	res := make([]int, 0)
    	res = append(res, root.Val)
    	if root.Left != nil {
    		res = append(res, PreOrderTraversal(root.Left)...)
    	}
    	if root.Right != nil {
    		res = append(res, PreOrderTraversal(root.Right)...)
    	}
    	return res
    }

    //非递归解法
    func PreOrderTraversal2(root *TreeNode) []int {
    	if root == nil {
    		return nil
    	}
    	stack := make([]*TreeNode, 0)
    	res := make([]int, 0)
    	//把根节点入栈
    	for root != nil || len(stack) > 0 {
            //不停的找做节点
    		for root != nil {
                //根节点先输出
    			res = append(res, root.Val)
    			stack = append(stack, root)
    			root = root.Left
    		}
            //出栈操作
    		root = stack[len(stack)-1]
    		stack = stack[:len(stack)-1]
            //遍历右节点
    		root = root.Right
    	}
    	return res
    }

中序遍历

中序遍历就是：先左节点 —> 根节点 —> 右节点

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
35
36
37
38
39
40
func InOrderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var ret []int
	lret := InOrderTraversal(root.Left)
	if len(lret) > 0 {
		ret = append(ret, lret...)
	}
	ret = append(ret, root.Val)
	rret := InOrderTraversal(root.Right)
	if len(rret) > 0 {
		ret = append(ret, rret...)
	}
	return ret
}

//中序遍历的非递归 --- 使用栈
func InOrderTraversal2(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	stack := make([]*TreeNode, 0)
	res := make([]int, 0)

	for root != nil || len(stack) > 0 {
		//把左子树一直入栈
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		//对左子树出栈
		root = stack[len(stack)-1]
		res = append(res, root.Val)
		stack = stack[:len(stack)-1]
		//有节点
		root = root.Right
	}
	return res
}

后序遍历

后序遍历就是：先左节点 —> 右节点 —> 根节点

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

//递归后序
func PostOrderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	res := make([]int, 0)
	if root.Left != nil {
		res = append(res, PostOrderTraversal(root.Left)...)
	}
	if root.Right != nil {
		res = append(res, PostOrderTraversal(root.Right)...)
	}
	res = append(res, root.Val)
	return res
}

//非递归：使用双栈法
func PostOrderTraversal2(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	//初始化一个栈
	stack := make([]*TreeNode, 0)
	//根节点入栈
	stack = append(stack, root)
	//结果集
	res := make([]int, 0)
	for len(stack) > 0 {
		//取栈顶元素
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if len(res) == 0 {
			res = append(res, node.Val)
		} else {
			//向slice 的头插入对应的值（类似双栈里面的第二个栈）
			res = append(res[:1], res[0:]...)
			res[0] = node.Val
		}

		if node.Left != nil {
			stack = append(stack, node.Left)
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	return res
}

层次遍历

层次遍历也可以叫做广度优先遍历，有几种解法，实现了其中的傀儡节点法

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
35
36
37
38
39
40
41
42
43
44
45
func LevelOrder(root *TreeNode) [][]int {
	list := make([]*TreeNode, 0)
	res := make([][]int, 0)

	if root == nil {
		return res
	}
	//加入头节点
	list = append(list, root)
	//加入傀儡节点（使用-1 作为傀儡节点）
	list = append(list, &TreeNode{
		Val: MinInt,
	})

	tmp := make([]int, 0)
	//表示不为空
	for len(list) > 0 {
		if list[0].Val == MinInt && list[0].Right == nil && list[0].Left == nil {
			//遍历到傀儡节点了，就在队列里面插入一个傀儡节点
			list = append(list, &TreeNode{
				Val: MinInt,
			})
			if len(tmp) > 0 {
				res = append(res, tmp)
				//重新初始化一个tmp,表示另一层
				tmp = make([]int, 0)
			} else {
				break
			}
		} else {
			//不是傀儡节点，就把左右节点分别入队
			tmp = append(tmp, list[0].Val)
			//有左右节点，先从做节点入队，然后是有节点
			if list[0].Left != nil {
				list = append(list, list[0].Left)
			}
			if list[0].Right != nil {
				list = append(list, list[0].Right)
			}
		}
		//把当前元素出队
		list = list[1:]
	}
	return res
}

类似求树的最大深度也可以用这个非递归的方式求解。

深度优先遍历

深度优先就可以使用先序遍历来实现

 上一页

select epoll