使用递归思想遍历二叉树

二叉树的遍历主要有两种方式：深度优先遍历和广度优先遍历
这篇主要讲使用深度优先遍历来遍历二叉树
深度优先遍历有以下三种
前、中、后序遍历，这三种遍历方式的主要区别是中间节点的位置所在的顺序
前序遍历：中间节点在叶子节点前面
中序遍历：中间节点在叶子节点中间
后续遍历：中间节点在叶子节点后面

本文主要以中序遍历为例讲解递归遍历二叉树的过程

type TreeNode struct {
	Val   int //值
	Left  *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	res := make([]int, 0)
	var traversal func(node *TreeNode)
	traversal = func(node *TreeNode) {
		if node == nil {
			return
		}
		traversal(node.Left)
		res = append(res, node.Val)
		traversal(node.Right)
	}
	traversal(root)
	return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20