递归在树的深度遍历中的运用

浅浅的花香味﹌ 2024-03-23 19:46 65阅读 0赞

## 树的深度遍历 ##

> 对于树这种数据结构，之前一直使用的是层次遍历，也就是**广度优先搜索的方式（BFS）**；对于树的遍历，还可以进行**深度优先搜索（DFS）**。
> 
> 而结合递归，树的深度优先搜索便能够很容易让人记住，面试官往往不会考简单的使用递归实现树的深度遍历，因此，除了使用递归方法外，非递归方式实现树的遍历也需要掌握（下期讲解）。

## 理解树的前中后序遍历 ##

> 深度优先遍历有 前 中 后 序 三种情况。和广度优先搜索一样，前中后序的遍历都主要看的是中间节点（根节点）的位置。
> 
> 通过二叉树的角度看递归。每次遇到递归，主要按照前面说的三步来写（或者加上第四步的验证）。递归只能处理当前层与下一层之间的关系，并不关心下层与下下层的关系。具体来说，有以下三步来分解递归：
> 
>  *  从小到大递推，找出递推公式
>  *  分情况讨论，明确终止条件
>  *  结合递推公式 + 终止条件，写出完整方法
>  *  （从大到小画图验证）

### 前序遍历 ###

#### 从小到大递推，找出递推公式 ####

> 以下述二叉树为例：
> 
> 3
> 
> / \\
> 
> 9 20
> 
> / \\
> 
> 15 7
> 
> 先选择一个最小的子树：
> 
> 20
> 
> / \\
> 
> 15 7
> 
> 如果root为20，则此时前序访问顺序就是：
> 
> void visit()\{
> 
> list.add(root); // 20被访问了
> 
> root.left; // 继续访问15
> 
> root.right;// 继续访问 7
> 
> \}
> 
> 再向上访问，看root为3的情况：
> 
> void visit()\{
> 
> list.add(root);// 3被访问了
> 
> list.left;// 9被访问了
> 
> list.right;// 20被访问了
> 
> \}

> 通过上述举例，20是一个树的根节点，3又是另一个树的根节点 ，而且两者的访问方式相同，所以可以直接合并到一起：
> 
> void visit()\{
> 
> list.add(root);
> 
> visit(root.left);
> 
> visit(root.right);
> 
> \}
> 
> 这就是递推方法

#### 分情况讨论，明确结束条件 ####

> 上面有了递归的主体，但是这个递归什么时候结束呢? 很明显应该是root=null的时候。一般来说链表和二叉树问题的终止条件都包含当前访问的元素为null。

#### 结合递推公式 + 终止条件，写出完整方法 ####

> 结合递推公式和终止条件，可写出完整的树的前序遍历方法，同时修改方法名，具体效果如下：

public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val +" ");
        preOrder(root.left);
        preOrder(root.right);
    }

#### 画图校验 ####

![image.png][]

### 中序遍历 ###

> 前序遍历理解后，中序和后序就容易理解了。中序遍历代码如下：

/**
         * 中序遍历
         * @param root 根节点
         */
        public void cenorder(TreeNode root){
            if (root == null){
                return;
            }
            cenorder(root.left);
            System.out.print(root.val+"  ");
            cenorder(root.right);
        }

### 后序遍历 ###

> 后序遍历代码如下

/**
         * 后序遍历
         * @param root 根节点
         */
        public void postOrder(TreeNode root){
            if (root == null){
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val + "  ");
        }

[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/0b3a27158f48468b9b3e0715792a1a8c.png