DFS的三种遍历方式

优先搜索二叉树

算法

发布日期: 2023-10-07

更新日期: 2023-10-07

文章字数: 2.1k

阅读时长: 8 分

阅读次数:

DFS的三种遍历方式

之前写过有关BFS和DFS的优先遍历方式的区别和联系。其中对BFS总结稍微详细一些，用到队列的数据结构，还有对层序遍历的用法分析。这次详细说说DFS的3种基础的遍历方式，可以将两者进行归纳总结一起来复习。

二叉树

树是一种比较常见的数据结构，其中核心是包括根和叶子，这些节点都是具有一定联系。而其中，最具有代表性的是二叉树。
二叉树。顾名思义，指的是树的分支最多存在两个流向。二叉树的根节点可能存在子节点，子节点又是对应子树的根节点。更为详尽地，子节点包含两个方向，一左一右。因此最好的处理方法是利用递归对二叉树各个节点流向进行遍历

数据结构类型定义如下：

public class TreeNode{
    int val;//节点的值
    TreeNode left;//左节点
    TreeNode right;//右节点
    
    TreeNode(int x){
        val=x;
    }
}

二叉树的DFS

本文探讨的是有关深度优先搜索的算法关系，DFS按照遍历的顺序可分为三类：
- 中序遍历（左、根、右）
- 前序遍历（根、左、右）
- 后序遍历（左、右、根）
对于深度优先搜索的遍历而言，由于是在一条路上走到头，再进行回溯重新走，所以一方面可以利用递归思想进行操作，另外一方面也可以用到迭代思想，利用栈的基本数据结构实现。本质上都相同，但是在代码量方面就存在很大的差异了。下面讨论的处理方式也分别用这两种方法进行实现。

1. 中序遍历

按照中序遍历的顺序，先遍历二叉树的左子树，然后遍历二叉树的根节点，最后是二叉树的右子树。对于上图子树的遍历而言，依次的顺序是:[4,2,5,1,6,3,7]

递归操作代码实现：

public List<Integer>inOrderTraversal(TreeNode root){
    List<Integer> nodes=new LinkedList<>();//由于最后返回的是列表[,,,],所以需要用到LinkedList
    dfs(root,nodes);
    return nodes;
}
public void dfs(TreeNode root,List<Integer>nodes){
    if(root!=null){
        dfs(root.left,nodes);
        nodes.add(root.val);
        dfs(root.right,nodes);
    }
}

可以看出上述的代码逻辑比较清晰，按照左、根、右的套路进行操作，但是如果二叉树的深度比较大（根节点到叶节点的最长路径的长度），我们进行左操作的次数太多的话，会导致栈溢出的问题，对空间浪费较为严重。
我们如果将递归换成迭代操作的话，需要引入栈的数据结构。对于中序遍历而言，我们在到达根节点的时候不进行遍历写入值的操作，而是进一步顺着左子节点找到叶节点，再进行回溯寻找父节点。这要求我们每次遍历二叉树的时候将遇到的每个节点都存储在栈中，方便查询。

迭代操作代码实现：

public List<Integer> inOrderTraversal(TreeNode root){
    List<Integer> nodes=new LinkedList<>();
    Stack<TreeNode> stack=new Stack<>();//引入栈的数据结构
    TreeNode cur=root;//cur表示当前的节点，位置位于root
    while(cur!=null || !stack.isEmpty()){//当前节点不为空，并且栈中存在元素值得时候
        while(cur!=null){
            stack.push(cur);//根元素入栈
            cur=cur.left;//指针向左
        }
        //当左遍历完成之后
        cur=stack.pop();//栈顶元素出栈，也就是最远的左子节点的位置元素出栈
        nodes.add(cur.val);//遍历，添加节点值
        cur=cur.right;//指针向右
    }
    return nodes;
}

这里有个思考：左子节点遍历完之后为什么指针就指向右节点了？之前理解存在误区，所谓的根节点，其实是对应这上一层的左节点。二叉树中实际只有左右两个分支和最初的root节点，只是我们按层进行划分的时候存在根和子的区别。

2. 前序遍历

按照前序遍历的顺序，先遍历二叉树的根节点，然后遍历二叉树的左子树，最后是二叉树的右子树。对于上图子树的遍历而言，依次的顺序是:[1,2,4,5,3,6,7]。

由于前序遍历和中序遍历的代码思考逻辑很像，这里就直接贴出两种方式的对应代码，进行比较即可。

递归操作代码实现：

public List<Integer>PreOrderTraversal(TreeNode root){
    List<Integer> nodes=new LinkedList<>();//由于最后返回的是列表[,,,],所以需要用到LinkedList
    dfs(root,nodes);
    return nodes;
}
public void dfs(TreeNode root,List<Integer>nodes){
    if(root!=null){
        nodes.add(root.val);//记录当前（根）节点的值
        dfs(root.left,nodes);
        dfs(root.right,nodes);
    }
}

迭代操作代码实现：

public List<Integer> inOrderTraversal(TreeNode root){
    List<Integer> nodes=new LinkedList<>();
    Stack<TreeNode> stack=new Stack<>();//引入栈的数据结构
    TreeNode cur=root;//cur表示当前的节点，位置位于root
    while(cur!=null || !stack.isEmpty()){//当前节点不为空，并且栈中存在元素值得时候
        while(cur!=null){
            nodes.add(cur.val);//遍历，添加节点值
            stack.push(cur);//根元素入栈
            cur=cur.left;//指针向左
        }
        //当左遍历完成之后
        cur=stack.pop();//栈顶元素出栈，也就是最远的左子节点的位置元素出栈
        cur=cur.right;//指针向右
    }
    return nodes;
}

3. 后序遍历

按照后序遍历的顺序，先遍历二叉树的左子树，然后遍历二叉树的右子树，最后是二叉树的根节点。对于上图子树的遍历而言，依次的顺序是:[4,5,2,6,7,3,1]。

递归操作代码实现：

public List<Integer>PreOrderTraversal(TreeNode root){
    List<Integer> nodes=new LinkedList<>();//由于最后返回的是列表[,,,],所以需要用到LinkedList
    dfs(root,nodes);
    return nodes;
}
public void dfs(TreeNode root,List<Integer>nodes){
    if(root!=null){
        dfs(root.left,nodes);
        dfs(root.right,nodes);
        nodes.add(root.val);//记录当前（根）节点的值
    }
}

和中序、前序遍历方法相比，后序遍历的迭代方法复杂一些。当到达某个节点时，如果之前没遍历过它的右子树就得遍历一下，遍历过了才可以遍历此节点。

如果此前右子树已经遍历过了，那么在右子树中最后一个遍历的节点应该是右子树的根节点，也就是当前节点的右子节点。

迭代操作代码实现：

public List<Integer> inOrderTraversal(TreeNode root){
      List<Integer> nodes=new LinkedList<>();
      Stack<TreeNode> stack=new Stack<>();//引入栈的数据结构
      TreeNode cur=root;//cur表示当前的节点，位置位于root
      
      TreeNode prev=null;//遍历过的前一个节点
      
      while(cur!=null || !stack.isEmpty()){//当前节点不为空，并且栈中存在元素值得时候
          while(cur!=null){
              stack.push(cur);//根元素入栈
              cur=cur.left;//指针向左
          }
          //当左遍历完成之后
          cur=stack.peek();//返回栈顶元素，但是并不出栈
          
          if(cur.right!=null && cur.right!=prev){//有右子树但是没遍历过
              cur=cur.right;//指针向右
              
          }else{//没有右子树或者右子树已经遍历过
              
              stack.pop();//栈顶元素出栈，也就是最远的左子节点的位置元素出栈
              nodes.add(cur.val);//遍历当前的值
              prev=cur;//指向当前的父节点
              cur=null;//cur清空
          }
     
      }
      return nodes;
  }

复杂度分析

时间复杂度

无论是哪种遍历算法，还是递归或迭代，如果此时的二叉树的节点个数为 $n$ ，那么此时的时间复杂度为 $O(n)$ 。因为总共需要遍历 $n$ 个节点。

空间复杂度

如果二叉树的深度为 $k$ ，那么空间复杂度为 $O(k)$ 。
在二叉树中，深度 $h$ 的取值范围是 $[log_2 n+1，n]$ 。也就是最小值为 $log_2 n+1$ ,最大值为 $n$ 。
- 举个简单的例子：
  
  包含7个节点的二叉树最少为 $3$ 层（每层分别为 $1，2，4$ ）；最多可能有 $7$ 层（每层都是 $1$ ）。