树、二叉树、二叉搜索树

二叉树的中序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func inorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var res []int
	_inorder(root, &res)
	return res
}

// left root right
func _inorder(root *TreeNode, res *[]int) {
	// 终止条件
	if root == nil {
		return
	}
	// 左子树
	_inorder(root.Left, res)
	//保存
	*res = append(*res, root.Val)
	// 右子树
	_inorder(root.Right, res)
}

二叉树的前序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func preorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var res []int
	_preorder(root, &res)
	return res
}

func _preorder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}
	*res = append(*res, root.Val)
	_preorder(root.Left, res)
	_preorder(root.Right, res)
}

N 叉树的后序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func postorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var res []int
	_postorder(root, &res)
	return res
}

func _postorder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}
	_postorder(root.Left, res)
	_postorder(root.Right, res)
	*res = append(*res, root.Val)
}

N 叉树的前序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func postorder(root *Node) []int {
	if root == nil {
		return nil
	}
	var res []int
	_nPostorder(root, &res)
	return res
}

func _nPostorder(root *Node, res *[]int) {
	if root == nil {
		return
	}
	for _, child := range root.Children {
		_nPostorder(child, res)
	}
	*res = append(*res, root.Val)
}

N 叉树的层序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func levelOrder(root *Node) [][]int {
	if root == nil {
		return nil
	}
	var res [][]int
	dfs(root, 0, &res)
	return res
}

func dfs(root *Node, level int, res *[][]int) {
	if root == nil {
		return
	}
	if len(*res) == level {
		*res = append(*res, []int{})
	}
	(*res)[level] = append((*res)[level], root.Val)
	for _, child := range root.Children {
		dfs(child, level+1, res)
	}
}

Contents