企业网站seo推广方案,网页生成pdf失败,石家庄免费做网站,江门网站设计文章目录 前言1. 最大深度问题2. 判断平衡树3. 最小深度4. N叉树的最大深度总结 前言 提示#xff1a;我的整个生命#xff0c;只是一场为了提升社会地位的低俗斗争。--埃莱娜费兰特《失踪的孩子》 这一关我们看一些比较特别的题目#xff0c;关于二叉树的深度和高度问题。这… 文章目录 前言1. 最大深度问题2. 判断平衡树3. 最小深度4. N叉树的最大深度总结 前言 提示我的整个生命只是一场为了提升社会地位的低俗斗争。--埃莱娜·费兰特《失踪的孩子》 这一关我们看一些比较特别的题目关于二叉树的深度和高度问题。这些对递归的考察更高些要注意了。 给你一个二叉树 我们看下力扣的相关题目这些是关于深度和高度的问题。
推荐题目⭐⭐⭐⭐
104. 二叉树的最大深度 - 力扣LeetCode
110. 平衡二叉树 - 力扣LeetCode
111. 二叉树的最小深度 - 力扣LeetCode
1. 最大深度问题
参考题目介绍104. 二叉树的最大深度 - 力扣LeetCode 首先最大深度根节点到最远叶子节点的最长路径上的节点数。说明叶子节点是没有子节点的。
我们看看下面这些。上图的最大深度为3 对于node(3)最大深度自然是左右子节点1左右子节点有可能为空只要有一个树的最大高度就是1 1 2。然后再增加几个节点 很显然相对于node(20)最大的深度自然是左右子节点1左右子节点有可能为空只要右一个树的最大高度就是1 1 2用代码表示就是
int depth 1 math(leftDepth,rightDepth);对于3则是左右子树深度最大的那个再加1具体谁的更大则不必管旭所以对于node(3)的逻辑判断就是
int leftDepth getDepth(root.left); //左
int rightDepth getDepth(root.right); // 右
int depth 1 math(leftDept,rightDept); // 中那么什么时候结束呢这里仍然是root null 返回0就行了至于入参自然是要处理的子树的根节点root而返回值则是当前root所在子树的最大高度所以合在一起就是 /*** 通过递归计算二叉树的深度** param root* return*/public static int maxDepth_1(TreeNode root) {if(root null) {return 0;}int leftDepth maxDepth_1(root.left);int rightDepth maxDepth_1(root.right);return Math.max(leftDepth, rightDepth) 1;}上面代码先拿到左右子树的结果再计算Math.max(left,right) 1本质上和后序遍历一样一次者可以看做事后序遍历的扩展问题。
我们继续看这个题目如果我们确定树最大有几层是不是也确定了最大深度呢当然另一个思路不就来了我们直接套用层序遍历的代码 具体细节注意一下我们这里获取层数每获取一层就加一。 /*** 通过层次遍历来求最大深度** param root* return*/public static int maxDepth_2(TreeNode root) {// 校验参数if (root null){return 0;}// 创建空间int res 0;QueueTreeNode queue new LinkedListTreeNode();// 根节点入队不断的遍历根节点queue.offer(root);while(!queue.isEmpty()){// 获取到每层多少个int size queue.size();// size 0 说明这一层遍历完了while(size 0){// 遍历TreeNode node queue.poll();if (node.left ! null){queue.offer(node.left);}if (node.right ! null){queue.offer(node.right);}size--;}res;}return res;}2. 判断平衡树
参考题目介绍110. 平衡二叉树 - 力扣LeetCode 补充一个知识点高度和深度怎么区分?
二叉树节点的深度从根节点到该节点的最长简单路径边的条数。二叉树节点的高度从该节点到叶子节点的最长简单路径边的条数。 关于根节点的深度是1还是0的问题不同的地方标准不一样力扣的题目中都是以根节点的深度为1其他的我们先不管。
我们接着看一下这个问题 很显然只要有两次的时候一定是平衡的因为对于node(3)左右孩子如果只有一个呢么高度差就是1如果左右孩子都没有或者都有则高度差为0。但是如果再加一层呢
看下图 对于node(3)需要同时知道自己左右子树的最大高度差是否 2.
当节点root左/右子树的高度差 2则返回节点root的左右子树中最大高度1maxleft,right) 1);参考上面的深度和高度对比图思考下这里为什么取最大高度当节点root左/右子树的高度差 2则返回-1代表此树已经不是平衡树了。
也是就是说
int left recur(root.left);
int right recur(root.right);
return Math.abs(left - right) 2 ? Math.max(left,right) 1:-1; 我们此时已经写出了核心代码假设子树已经不平衡了我们就不需要再递归下去而是直接返回就行了。例如这个树中的节点20 综合考虑几种情况我们看下完整的代码 /*** 方法1 自下而上** param root* return*/public static boolean isBalanced_1(TreeNode root) {return recur(root) -1;}public static int recur(TreeNode root) {if (root null){return 0;}int left recur(root.left);if (left -1){return -1;}int right recur(root.right);if (right -1){return -1;}return Math.abs(left - right) 2 ? Math.max(left,right) 1: -1;}/*** 2.自上而下** param root* return*/public static boolean isBalanced_2(TreeNode root) {if (root null){return true;}return Math.abs(depth(root.left) - depth(root.right)) 1 isBalanced_2(root.left) isBalanced_2(root.right);}public static int depth(TreeNode root){if (root null){return 0;}return Math.max(depth(root.left),depth(root.right)) 1;}3. 最小深度
参考题目介绍111. 二叉树的最小深度 - 力扣LeetCode 既然有最大深度可能会有最小深度这不他就来了怎么找出最小深度呢
最小深度从根节点到最接近叶子节点的最短路径上的节点数量。
看下下面这个特殊例子 答案是 2 【说明】叶子节点是指没有子节点的节点。 前面两道题涉及到最大深度这里讲max改成min是不是就可以解决了呢 不行你注意看上图
这里的关键问题是题目中说的最小深度是从根节点到最近叶子节点的最短路径上的节点数量也就是说最小深度的一层必须要有叶子节点不能直接使用。
这里的核心问题仍然是终止条件分析
如果左子树为空右子树不为空说明最小深度是1 右子树的深度。反之右子树为空左子树不为空最小深度1 左子树的深度。
最后如果左右子树都不空返回左右子树深度最小值1。
我们看下代码展示 /*** 通过递归计算二叉树的最小** param root* return*/public static int minDepth_1(TreeNode root) {if (root null){return 0;}// 根if (root.left null root.right null){return 1;}// 左int min_depth Integer.MAX_VALUE;if (root.left ! null){min_depth Math.min(minDepth_1(root.left),min_depth);}// 右if (root.right ! null){min_depth Math.min(minDepth_1(root.right),min_depth);}return min_depth 1;}除了递归方式我们也可以采用层次遍历只要再遍历时第一次遇到叶子节点就直接返回其所在的层次就行我们可以简单改下层序遍历的方法 /*** 通过层次遍历来求最大深度** return*/public static int minDepth_2(TreeNode root) {// 参数检验if (root null){return 0;}// 创建空间int minDepth 0;QueueTreeNode queue new LinkedList();// 根节点入队不断循环遍历queue.offer(root);while(!queue.isEmpty()){// 获取队列的长队 这个长度说明这一层有多少个节点int size queue.size();minDepth;for(int i 0; i size; i){TreeNode node queue.poll();if (node.left null node.right null){return minDepth;}if (node.left ! null){queue.offer(node.left);}if (node.right ! null){queue.offer(node.right);}}}return 0;}4. N叉树的最大深度
参考题目介绍559. N 叉树的最大深度 - 力扣LeetCode 这道题不同的地方是将二叉树换成了N叉树N叉树的节点较多我们使用List存储遍历时采用for即可我们先看看力扣的N叉树的定义
class Node {public int val;public ListNode children;public Node() {}public Node(int _val) {val _val;}public Node(int _val, ListNode _children) {val _val;children _children;}
};这个题的实现和上个题的最大区别就是在处理子树的问题上面加了个处理List的for循环
代码也很简单 /*** 递归求N叉树的深度* param root* return*/public static int maxDepth_N(NTreeNode root) {if (root null){return 0;}else if (root.children.isEmpty()){return 1;}else{// 处理子树问题ListInteger heights new ArrayList();for(NTreeNode item : root.children){heights.add(maxDepth_N(item));}return Collections.max(heights) 1;}}当然了本地还可以使用层序遍历这个作为拓展感兴趣的话可以试试。 总结
提示二叉树的深度和高度N叉树的深度问题平衡树的判断问题
