力扣二叉树基础之深度优先遍历

发表于

本文主要介绍LeetCode上关于二叉搜索树的题目。

本文主要介绍二叉树的深度优先（DFS）遍历其实就是递归遍历。

关键词：二叉树，递归遍历

什么是递归

二叉树是什么，相信大家都知道，这里不在赘述。这里主要介绍函数的递归调用。

递归函数三要素

既然前人已经替我们总结了经验，那我们直接切入正题。

三要素指的是：

  1. 确定递归函数的参数和返回值
  2. 确定终止条件
  3. 确定单层递归函数的逻辑

以二叉树的前序（迭代）遍历为例

  1. 确定递归函数的参数和返回值：遍历主要就是返回二叉树节点的值，因此参数就是二叉节点；
  2. 确定终止条件，终止条件就是节点为空；
  3. 确定单层递归的逻辑：前序遍历指的是Node->Left->Right，即中、左、右，因此代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func preorder(root *TreeNode) (res []int) {
    var worker func(node *TreeNode) // 递归函数
    worker = func (node *TreeNode) {
        if root == nil {
            return 
        }
        res = append(res, node.Val) // 中
        worker(node.Left)           // 左
        worker(node.Right)          // 右
    }
    worker(root)
    return
}

中序（迭代）遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
func inorder(root *TreeNode) (res []int) {
    var worker func(node *TreeNode)
    worker = func(node *TreeNode){
        if root == nil {
            return
        }
        worker(node.Left)
        res = append(res, node.Val)
        worker(node.Right)
    }
    worker(root)
    return 
}

后序（迭代）遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
func postorder(root *TreeNode) (res []int) {
    var worker func(root *TreeNode)
    worker = func(node *TreeNode) {
        if root == nil {
            return
        }
        worker(node.Left)
        worker(node.Right)
        res = append(res, node.Val)
    }
    worker(root)
    return
}

题目

未完待续