广度优先、深度优先

 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 levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	var res [][]int
	dfs(root, 0, &res)
	return res
}

func dfs(root *TreeNode, level int, res *[][]int) {
	if root == nil {
		return
	}
	if level == len(*res) {
		*res = append(*res, []int{})
	}
	(*res)[level] = append((*res)[level], root.Val)
	if root.Left != nil {
		dfs(root.Left, level+1, res)
	}
	if root.Right != nil {
		dfs(root.Right, level+1, 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


func levelOrder(root *TreeNode) [][]int {
	return bfs(root)
}

func bfs(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	var res [][]int
	var levelQueue []*TreeNode
	// 当前需要遍历的层， 将当前层上的node都放到queue中
	levelQueue = append(levelQueue, root)
	// 层数计数
	for i := 0; len(levelQueue) > 0; i++ {
		res = append(res, []int{})
		// 用来存放下一层的Node
		var nextLevel []*TreeNode
		for _, node := range levelQueue {
			// 将当前层的值保存到对应的i中去
			res[i] = append(res[i], node.Val)
			// 下层的node保存下来
			if node.Left != nil {
				nextLevel = append(nextLevel, node.Left)
			}
			if node.Right != nil {
				nextLevel = append(nextLevel, node.Right)
			}
		}
		// 用以下层再次遍历，也作为跳出条件
		levelQueue = nextLevel
	}
	return res
}

Contents