二叉树的三种遍历 - sheep44044的小站

二叉树#

给你二叉树的根节点 root ，返回它节点值的 前/中/后序 遍历。

示例 1：

1
输入：root = [1,null,2,3]
2
输出：

示例 2：

1
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

示例 3：

1
输入：root = []
2
输出：[]

示例 4：

1
输入：root = [1]
2
输出：[1]

前序遍历

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func preorderTraversal(root *TreeNode) []int {
10
    res := []int{}
11
    var dfs func(*TreeNode)
12
    dfs = func(node *TreeNode){
13
        if node == nil {
14
            return
15
        }
16

17
        res = append(res, node.Val)
18
        dfs(node.Left)
19
        dfs(node.Right)
20
    }
21
    dfs(root)
22

23
    return res
24
}

中序遍历

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func inorderTraversal(root *TreeNode) []int {
10
    res := []int{}
11
    var dfs func(*TreeNode)
12
    dfs = func(node *TreeNode) {
13
        if node == nil {
14
            return
15
        }
16

17
        dfs(node.Left)
18
        res = append(res, node.Val)
19
        dfs(node.Right)
20
    }
21
    dfs(root)
22

23
    return res
24
}

后序遍历

1
/**
2
 * Definition for a binary tree node.
3
 * type TreeNode struct {
4
 *     Val int
5
 *     Left *TreeNode
6
 *     Right *TreeNode
7
 * }
8
 */
9
func postorderTraversal(root *TreeNode) []int {
10
    res := []int{}
11
    var dfs func(*TreeNode)
12
    dfs = func(node *TreeNode){
13
        if node == nil {
14
            return
15
        }
16

17
        dfs(node.Left)
18
        dfs(node.Right)
19
        res = append(res, node.Val)
20
    }
21
    dfs(root)
22

23
    return res
24
}