LeetCode 0144.二叉树的前序遍历

二叉树的前序遍历

题目描述

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

思路

二叉树主要有两种遍历方式：

深度优先遍历：先往深走，遇到叶子节点再往回走
- 前序遍历（递归法，迭代法）：中左右
- 中序遍历（递归法，迭代法）：左中右
- 后序遍历（递归法，迭代法）：左右中
广度优先遍历：一层一层的去遍历
- 层次遍历（迭代法）

在深度优先遍历中：有三个顺序，前中后序遍历，这里前中后，其实指的就是中间节点的遍历顺序。

二叉树相关题目，经常会使用递归的方式来实现深度优先遍历
因为栈是递归的一种实现结构，所以深度优先遍历其实也可以借助栈使用非递归的方式来实现的
广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的

递归算法的三个要素：

确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
确定终止条件：写完了递归算法,，运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

代码

Go

 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


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

// 前序遍历
func preorderTraversal(root *TreeNode) []int {
    // 存储遍历的节点值
    res := []int{}
    // 声明用于前序递归遍历的匿名函数 无返回值
    var traversal func(node *TreeNode)
    // 初始化用于前序递归遍历的匿名函数 无返回值
    traversal = func(node *TreeNode) {
        if node == nil {
            // 递归结束条件:节点为空
            return
        }
        res = append(res, node.Val)
        traversal(node.Left)
        traversal(node.Right)
    }
    traversal(root)
    return res
}

// 中序遍历
func inorderTraversal(root *TreeNode) []int {
    // 存储遍历的节点值
    res := []int{}
    // 声明用于中序递归遍历的匿名函数 无返回值
    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
}

// 后序遍历
func postorderTraversal(root *TreeNode) []int {
    // 存储遍历的节点值
    res := []int{}
    // 声明用于后序递归遍历的匿名函数 无返回值
    var traversal func(node *TreeNode)
    // 初始化用于后序递归遍历的匿名函数 无返回值
    traversal = func(node *TreeNode) {
        if node == nil {
            // 递归结束条件:节点为空
            return
        }
        traversal(node.Left)
        traversal(node.Right)
        res = append(res, node.Val)
    }
    traversal(root)
    return res
}

Link

GitHub