二叉树的最小深度
- leetcode111. 二叉树的最小深度
- 题目描述
- DFS 深度优先遍历
- 解题思路
- 代码演示
- BFS 广度优先遍历
- 解题思路
- 代码演示
- 往期经典
leetcode111. 二叉树的最小深度
题目描述
DFS 深度优先遍历
解题思路
|
从根节点看,没有右树.这种情况下最小深度就是左树的深度4,因此代码里要对,没有左树和没有右树的情况做下判断.
代码演示
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public int minDepth(TreeNode root) {if(root == null){return 0;}return process(root);}/*** dfs 深度优先遍历*/public int process(TreeNode root){//base case if(root == null){return 0;}//没有左右节点时,返回1,高度就是节点本身if(root.left == null && root.right == null){return 1;}int left = process(root.left);int right = process(root.right);//没有左树的情况if(left == 0 && right != 0){return right + 1;}//没有右树的情况if(left != 0 && right == 0){return left + 1;}//左树右树都有的情况下,返回最小深度加1return Math.min(left,right) + 1;}
}
BFS 广度优先遍历
解题思路
代码演示
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public int minDepth(TreeNode root) {if(root == null){return 0;}return bfs(root);}/*** BFS */public int bfs(TreeNode root){Queue<TreeNode> queue = new LinkedList<>();//根节点加进去queue.offer(root);//跟节点本身的高度是1,所有深度初始化1 int depth = 1;//开始遍历while(!queue.isEmpty()){//每层的宽度int N = queue.size();//把一层遍历完for(int i = 0; i < N ;i++){TreeNode cur = queue.poll();//如果左右节点都是null 代表这个节点结束了,第一个结束的就是最小深度,直接返回if(cur.left == null && cur.right == null){return depth;}//左右节点加进去if(cur.left != null){queue.offer(cur.left);}if(cur.right != null){queue.offer(cur.right);}}//遍历完一层深度加1depth++;}return depth;}
}
往期经典
leetcode46. 全排列
leetcode39. 组合总和
leetcode216. 组合总和 III
leetcode90. 子集 II
leetcode40. 组合总和 II
leetcode77. 组合
leetcode78 子集
leetcode47. 全排列 II
本文链接：https://my.lmcjl.com/post/13974.html
展开阅读全文
4 评论