DFS深度优先搜索

文章目录

DFS深度优先搜索
- 1. 算法思想
- 2. 步骤理解
- 3. 例题
- - 3.1 **二叉树的最大深度**
  - 3.2 **将升序数组转化为平衡二叉搜索树**
  - 3.3 **判断是不是平衡二叉树**
  - 3.4 **二叉树的后序遍历**
  - 3.5 **二叉树的直径**

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}

返回值：

示例2

输入：

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

复制

返回值：

题解

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 hereif(root == null){return 0;}int left = maxDepth(root.left);  //计算根节点左子树的深度int right = maxDepth(root.right);  //计算根节点右子树的深度return Math.max(left, right)+1;  //取左子树深度和右子树深度二者中的最大值}
}

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

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

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}，如下图所示：

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

返回任意一种即可。

示例1

输入：

[-1,0,1,2]

返回值：

{1,0,2,-1}

示例2

输入：

[]

返回值：

{}

题解

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时，直接返回nullif (nums.length == 0) {return null;}return process(nums, 0, nums.length - 1);}public TreeNode process(int[] nums, int l, int r){//左边界大于右边界，一个元素都没有，不存在节点，返回nullif(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;}
}

3.3 判断是不是平衡二叉树

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

描述

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

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

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

样例解释：

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

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

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

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

输入描述：

输入一棵二叉树的根节点

返回值描述：

输出一个布尔类型的值

示例1

输入：

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

返回值：

true

示例2

输入：

{}

返回值：

true

题解

计算根节点左子树的深度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){//节点为空，深度为0if(root == null){return 0;}//计算该节点左子树的深度int left = getDepth(root.left);//计算该节点右子树的深度int right = getDepth(root.right);//返回左子树深度和右子树深度二者中的最大值，为以该节点为根节点的二叉树深度return left > right ? left+1 : right+1;}
}

3.4 二叉树的后序遍历

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

描述

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

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

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

样例图

示例1

输入：

{1,#,2,3}

返回值：

[3,2,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 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中的元素按顺序赋给数组resfor(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);}
}

3.5 二叉树的直径

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

描述

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

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

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

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

4.树为空时，返回 0

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

那么：

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

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

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

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

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

示例1

输入：

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

返回值：

示例2

输入：

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

返回值：

示例3

输入：

{1,2,3}

返回值：

题解

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

求某节点高度：

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

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 hereif(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;}
}