当前位置:   article > 正文

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

二叉树深度优先搜索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
推荐阅读
相关标签
  

闽ICP备14008679号