devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

DFS深度优先搜索_二叉树深度优先搜索dfs

作者：IT小白 | 2024-07-27 01:07:01

赞

踩

二叉树深度优先搜索dfs

DFS深度优先搜索

文章目录

1. 算法思想

  • 一直往深处走，无路可走，进行回溯
  • 不撞南墙不回头

2. 步骤理解

假设我们以向左边为先

  • 1） 从起始点A一直向左节点走，往最深处走，走到H

    外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

  • 2）走到H——》无路可走，进行回溯——》返回上一层到D

    在这里插入图片描述

  • 发现D节点还有路往深处走，走到 I

    在这里插入图片描述

  • 走到H——》无路可走，进行回溯——》返回上一层到D ——》D也无路可走，进行回溯 ——》返回上一层到B

    外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

  • …… ……不断重复这个过程

    就能遍历所有节点

3. 例题

3.1 二叉树的最大深度

题源：二叉树的最大深度_牛客题霸_牛客网 (nowcoder.com)

描述

求给定二叉树的最大深度，

深度是指树的根节点到任一叶子节点路径上节点的数量。

最大深度是所有叶子节点的深度的最大值。

（注：叶子节点是指没有子节点的节点。）

数据范围：0≤n≤100000，树上每个节点的val满足 ∣val*|≤100
要求： 空间复杂度 O(1),时间复杂度 O*(*n)

示例1

输入：

{1,2}

  • 1

返回值：

2

  • 1

示例2

输入：

{1,2,3,4,#,#,5}

  • 1

复制

返回值：

3

  • 1

题解

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        if(root == null){
            return 0;
        }

        int left = maxDepth(root.left);  //计算根节点左子树的深度
        int right = maxDepth(root.right);  //计算根节点右子树的深度

        return Math.max(left, right)+1;  //取左子树深度和右子树深度二者中的最大值
    }
}

  • 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

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

1. 判断节点1是否为空节点，不为空 ——> 计算节点1的left，进入递归，节点1的左节点是节点2 ——> 
2. 判断节点2是否为空节点，不为空 ——> 计算节点2的left，进入递归，节点2的左节点是节点4 ——> 
3. 判断节点4是否为空节点，不为空 ——> 计算节点4的left，进入递归，节点4的左节点无左节点：null ——>
4. 判断null是否为空，为空 ——> 返回0，即返回到上一层节点4处的left：0 ——> 
5. 计算节点4的right ——> 进入maxDepth()方法 ——> 判断节点4的右节点是否为空，为空 ——> 返回0，即节点4处的right：0 ——>
6. return Math.max(left, right)+1，节点4处的left和right都是0，则返回1，即返回到上一层节点2处的left: 1 ——>
7. 计算节点2的right ——> 进入maxDepth()方法 ——> 判断节点2的右节点是否为空，为空 ——> 返回0，即节点2处的right：0 ——>
8. return Math.max(left, right)+1，节点2处的left为1，right为0，则返回2，即返回到上一层节点1处的left: 2 ——>

9. ......然后接着上述步骤计算根节点右子树的深度

10. 最后返回左子树深度和右子树深度中最大值+1

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

3.2 将升序数组转化为平衡二叉搜索树

题源：将升序数组转化为平衡二叉搜索树_牛客题霸_牛客网 (nowcoder.com)

描述

给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.

平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1

数据范围：0≤n≤10000，数组中每个值满足∣val∣≤5000
进阶：空间复杂度 O*(n) ，时间复杂度O(*n)

例如当输入的升序数组为[-1,0,1,2]时，转化后的平衡二叉搜索树（BST）可以为{1,0,2,-1}，如下图所示：

img

或为{0,-1,1,#,#,#,2}，如下图所示：

img

返回任意一种即可。

示例1

输入：

[-1,0,1,2]

  • 1

返回值：

{1,0,2,-1}

  • 1

示例2

输入：

[]

  • 1

返回值：

{}

  • 1

题解

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return TreeNode类
     */
    public TreeNode sortedArrayToBST (int[] nums) {
        // write code here
        //当数组长度为0时，直接返回null
        if (nums.length == 0) {
            return null;
        }

        return process(nums, 0, nums.length - 1);
    }

    public TreeNode process(int[] nums, int l, int r){
        //左边界大于右边界，一个元素都没有，不存在节点，返回null
        if(l > r){
            return null;
        }

        //左边界等于右边界，只存在一个元素，将其当做节点值创建节点返回
        if(l == r){
            TreeNode root = new TreeNode(nums[l]);
            return root;
        }

        int mid = l+(r-l)/2;//中点下标，此下标志值就是根节点的值
        TreeNode root = new TreeNode(nums[mid]);

        //通过递归调用process()方法，找出根节点的左子树
        root.left = process(nums, l, mid-1);
        //通过递归调用process()方法，找出根节点的右子树
        root.right = process(nums, mid+1, r);

        return root;
    }
}

  • 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

3.3 判断是不是平衡二叉树

题源判断是不是平衡二叉树_牛客题霸_牛客网 (nowcoder.com)

描述

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

样例解释：

img

样例二叉树如图，为一颗平衡二叉树

注：我们约定空树是平衡二叉树。

数据范围：n≤100,树上节点的val值满足 0≤n≤1000

要求：空间复杂度O*(1)，时间复杂度 O*(n)

输入描述：

输入一棵二叉树的根节点

返回值描述：

输出一个布尔类型的值

示例1

输入：

{1,2,3,4,5,6,7}

  • 1

返回值：

true

  • 1

示例2

输入：

{}

  • 1

返回值：

true

  • 1

题解

计算根节点左子树的深度import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here
        // 特殊：当该二叉树为空时，是平衡二叉树
        if(pRoot == null){
            return true;
        }
        int left = getDepth(pRoot.left);//左子树深度
        int right = getDepth(pRoot.right);//右子树深度

        //左右两个子树的高度差的绝对值超过1时，不是平衡二叉树
        if(Math.abs(left-right) > 1){
            return false;
        }

        //左右两个子树的高度差的绝对值不超过1时，判断其左右两个子树是否都是一棵平衡二叉树
        return IsBalanced_Solution(pRoot.left)==true && IsBalanced_Solution(pRoot.right)==true;
    }

    //获取以某节点为根节点的二叉树深度
    public int getDepth(TreeNode root){
        //节点为空，深度为0
        if(root == null){
            return 0;
        }

        //计算该节点左子树的深度
        int left = getDepth(root.left);
        //计算该节点右子树的深度
        int right = getDepth(root.right);

        //返回左子树深度和右子树深度二者中的最大值，为以该节点为根节点的二叉树深度
        return left > right ? left+1 : right+1;
    }
}

  • 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

3.4 二叉树的后序遍历

题源：二叉树的后序遍历_牛客题霸_牛客网 (nowcoder.com)

描述

给定一个二叉树，返回他的后序遍历的序列。

后序遍历是值按照 左节点->右节点->根节点 的顺序的遍历。

数据范围：二叉树的节点数量满足 1≤n≤100 ，二叉树节点的值满足1≤val≤100 ，树的各节点的值各不相同

样例图

img

示例1

输入：

{1,#,2,3}

  • 1

返回值：

[3,2,1]

  • 1

说明：

如题面图  

  • 1

示例2

输入：

{1}

  • 1

返回值：

[1]

  • 1

题解

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {
        // write code here
        // 特殊：这颗二叉树为空
        if(root == null){
            return new int[0];
        }

        List list = new ArrayList(); //通过列表来先按后序遍历的元素进行存储
        post(list,root); // 进入递归，把元素按后序遍历进入list中
        int[] res = new int[list.size()]; //新建数组，最后返回

        //将列表list中的元素按顺序赋给数组res
        for(int i = 0; i < list.size(); i++){
            res[i] = (int) list.get(i);
        }
        
        return res;
    }

    // 递归找到按后序进入数组的元素
    public void post(List list, TreeNode node){
        if(node.left != null){
            post(list, node.left);
        }

        if(node.right != null){
            post(list, node.right);
        }

        list.add(node.val);
    }
}

  • 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

3.5 二叉树的直径

题源：二叉树的直径_牛客题霸_牛客网 (nowcoder.com)

描述

给定一颗二叉树，求二叉树的直径。

1.该题的直径定义为：树上任意两个节点路径长度的最大值

2.该题路径长度定义为：不需要从根节点开始，也不需要在叶子节点结束，也不需要必须从父节点到子节点，一个节点到底另外一个节点走的边的数目

3.这个路径可能穿过根节点，也可能不穿过

4.树为空时，返回 0

如，输入{1,2,3,#,#,4,5}，二叉树如下:

img

那么：

从4到5的路径为4=>3=>5，路径长度为2

从4到2的路径为4=>3=>1=>2，路径长度为3

如，输入{1,2,3,#,#,4,5,9,#,#,6,#,7,#,8}，二叉树如下:

img

那么路径长度最长为:7=>9=>4=>3=>5=>6=>8，长度为6

数据范围：节点数量满足 0≤n≤100

示例1

输入：

{1,2,3,#,#,4,5}

  • 1

返回值：

3

  • 1

示例2

输入：

{1,2,3,#,#,4,5,9,#,#,6,#,7,#,8}

  • 1

返回值：

6

  • 1

示例3

输入：

{1,2,3}

  • 1

返回值：

2

  • 1

题解

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

求某节点高度：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int diameterOfBinaryTree (TreeNode root) {
        // write code here
        if(root == null){
            return 0;
        }

        int d = get_hight(root.left)+get_hight(root.right);//获取以该节点为根节点的树的最大直径

        int max_d = Math.max(Math.max(d, diameterOfBinaryTree(root.left)), diameterOfBinaryTree(root.right));
        return max_d;
    }

    // 求某节点高度
    public int get_hight(TreeNode node){
        if(node == null){
            return 0;
        }

        int l = get_hight(node.left);
        int r = get_hight(node.right);

        return l>r ? l+1 : r+1;
    }
}

  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/887999
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号