Day26——二叉树专题 青旅半醒 2024-04-01 14:28 67阅读 0赞 #### 文章目录 #### * * * * 8.二叉树的最小深度 * 9.完全二叉树的节点个数 * 10.平衡二叉树 * 1.递归法 * 2.迭代法 -------------------- ##### 8.二叉树的最小深度 ##### **思路：** 左子树为空，右子树不为空，最小深度就是右子树的深度+1； 左子树不为空，右子树为空，最小深度就是左子树的深度+1； **代码实现：** class Solution { public int minDepth(TreeNode root) { if(root==null){ return 0; } int leftDepth = minDepth(root.left); int rightDepth = minDepth(root.right); if(root.left==null&&root.right!=null){ return 1+rightDepth; } if(root.right==null&&root.left!=null){ return 1+leftDepth; } return Math.min(leftDepth,rightDepth)+1; } } ##### 9.完全二叉树的节点个数 ##### **1.通用递归法** class Solution { public int countNodes(TreeNode root) { if(root==null){ return 0; } int leftNum = countNodes(root.left); int rightNum = countNodes(root.right); return leftNum+rightNum+1; } } **2.迭代法** class Solution { public int countNodes(TreeNode root) { if(root==null){ return 0; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int result = 0; while(!queue.isEmpty()){ int size = queue.size(); while(size-->0){ TreeNode cur = queue.poll(); result++; if(cur.left!=null){ queue.offer(cur.left); } if(cur.right!=null){ queue.offer(cur.right); } } } return result; } } **3.针对完全二叉树的解法** class Solution { /** * 针对完全二叉树的解法 * * 满二叉树的结点数为：2^depth - 1 */ public int countNodes(TreeNode root) { if(root == null) { return 0; } int leftDepth = getDepth(root.left); int rightDepth = getDepth(root.right); if (leftDepth == rightDepth) { // 左子树是满二叉树 // 2^leftDepth其实是 （2^leftDepth - 1） + 1 ，左子树 + 根结点 return (1 << leftDepth) + countNodes(root.right); } else { // 右子树是满二叉树 return (1 << rightDepth) + countNodes(root.left); } } private int getDepth(TreeNode root) { int depth = 0; while (root != null) { root = root.left; depth++; } return depth; } } ##### 10.平衡二叉树 ##### \*\*求高度：\*\*后序—自底向上 **求深度**：前序—自上向下 * 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。 * 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。 **补充：** ![image-20221103213521082][] **思路：** 使用后序，分别求出左右子树高度差，来判断左右子树高度差的绝对值是否大于1，大于1的话就不是平衡二叉树。只有知道左右子树的高度，才能来判断是否为平衡二叉树，所以遍历顺序是左右中。选择后序遍历。 ##### 1.递归法 ##### **代码实现：** class Solution { /** * 递归法 */ public boolean isBalanced(TreeNode root) { return getHeight(root) != -1; } private int getHeight(TreeNode root) { if (root == null) { return 0; } int leftHeight = getHeight(root.left); if (leftHeight == -1) { return -1; } int rightHeight = getHeight(root.right); if (rightHeight == -1) { return -1; } // 左右子树高度差大于1，return -1表示已经不是平衡树了 if (Math.abs(leftHeight - rightHeight) > 1) { return -1; } return Math.max(leftHeight, rightHeight) + 1; } } ##### 2.迭代法 ##### **代码实现：** class Solution { /** * 迭代法，效率较低，计算高度时会重复遍历 * 时间复杂度：O(n^2) */ public boolean isBalanced(TreeNode root) { if (root == null) { return true; } Stack<TreeNode> stack = new Stack<>(); TreeNode pre = null; while (root!= null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } TreeNode inNode = stack.peek(); // 右结点为null或已经遍历过 if (inNode.right == null || inNode.right == pre) { // 比较左右子树的高度差，输出 if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) { return false; } stack.pop(); pre = inNode; root = null;// 当前结点下，没有要遍历的结点了 } else { root = inNode.right;// 右结点还没遍历，遍历右结点 } } return true; } [image-20221103213521082]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9848279b3f3841da8b677698ca62ddf4.png
相关 Day30——二叉树专题 文章目录 22.验证二叉搜索树 23.二叉搜索树的最小绝对差 24.二叉搜索树中的插入 谁借莪１个温暖的怀抱￠/ 2024年04月01日 15:23/ 0 赞/ 51 阅读
妖狐艹你老母
╰+攻爆jí腚メ
Myth丶恋晨
我会带着你远行
系统管理员
港控/mmm°
还没有评论，来说两句吧...