[LeetCode] 110. Balanced Binary Tree ☆(二叉树是否平衡)
2023-09-14 09:07:35 时间
描述
解析
递归分别判断每个节点的左右子树
该题是Easy的原因是该题可以很容易的想到时间复杂度为O(n^2)的方法。即按照定义,判断根节点左右子树的高度是不是相差1,递归判断左右子树是不是平衡的。
根据深度判断左右子树是否平衡
在计算树的高度的同时判断该树是不是平衡的。
即,先判断子树是不是平衡的,若是,则返回子树的高度;若不是,则返回一个非法的数字,如负数。
当一个节点是左右子树有一个不是平衡二叉树则不必继续计算,直接返回false;当左右子树都是平衡时,再比较两个子树的高度是否相差1。若不是,则返回false,否则返回该节点的高度。
代码
递归分别判断每个节点的左右子树
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int depth (TreeNode root) { if (root == null) { return 0; } return Math.max(depth(root.left), depth(root.right)) + 1; } public boolean isBalanced (TreeNode root) { if (root == null) { return true; } int left = depth(root.left); int right = depth(root.right); return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right); } }
根据深度判断左右子树是否平衡
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isBalanced(TreeNode root) { return height(root) != -1; } private int height(TreeNode node){ if(null == node) return 0; int left = height(node.left); if(left == -1) return -1; int right = height(node.right); if(right == -1) return -1; if(Math.abs(left - right) > 1) return -1; return Math.max(left, right) + 1; } }
相关文章
- Java实现 LeetCode 784 字母大小写全排列(DFS)
- Java实现 LeetCode 655 输出二叉树(DFS+二分)
- Java实现 LeetCode 563 二叉树的坡度(又是一个遍历树)
- Java实现 LeetCode 301 删除无效的括号
- Java实现 LeetCode 260 只出现一次的数字 III(三)
- Java实现 LeetCode 236 二叉树的最近公共祖先
- Java实现 LeetCode 222 完全二叉树的节点个数
- Java实现 LeetCode 109 有序链表转换二叉搜索树
- Java实现 LeetCode 22 括号生成
- Java实现LeetCode_0013_RomanToInteger
- LeetCode(105):从前序与中序遍历序列构造二叉树
- LeetCode: 103_Binary Tree Zigzag Level Order Traversal | 二叉树Zigzag层次遍历 | Medium
- LeetCode(124):二叉树中的最大路径和
- leetcode 106. 从中序与后序遍历序列构造二叉树
- 【LeetCode Python实现】6. Z 字形变换(中等)
- 【LeetCode 中等 树 python3】144. 二叉树的前序遍历
- [LeetCode] 108. Convert Sorted Array to Binary Search Tree ☆(升序数组转换成一个平衡二叉树)
- [LeetCode] 112. Path Sum ☆(二叉树是否有一条路径的sum等于给定的数)
- [LeetCode] 104. Maximum Depth of Binary Tree ☆(二叉树的最大深度)
- LeetCode之Binary Tree Level Order Traversal 层序遍历二叉树
- leetcode 492. Construct the Rectangle
- leetcode 412. Fizz Buzz
- 【Leetcode刷题Python】145. 二叉树的后序遍历
- 【Leetcode刷题Python】110. 平衡二叉树
- LeetCode 94. 二叉树的中序遍历
- LeetCode 104. 二叉树的最大深度
- 【LeetCode】124.二叉树中的最大路径和