html网站源代码下载,dw做网站表格插不到右边,大庆市建设局网站,毕设电商网站设计给定一个二叉树#xff0c;判断它是否是高度平衡的二叉树。
本题中#xff0c;一棵高度平衡二叉树定义为#xff1a; 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,15,7]
输出#xff1a;t…给定一个二叉树判断它是否是高度平衡的二叉树。
本题中一棵高度平衡二叉树定义为 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1 输入root [3,9,20,null,null,15,7]
输出true示例 2 输入root [1,2,2,3,3,null,null,4,4]
输出false示例 3
输入root []
输出true提示
树中的节点数在范围 [0, 5000] 内-104 Node.val 104
解法 /*** 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 boolean isBalanced(TreeNode root) {if (root null) {return true;}else{//求根节点左子树和右子树的差值的绝对值如果小于1则为平衡二叉树return Math.abs(Bfs(root.left) - Bfs(root.right)) 1 isBalanced(root.left) isBalanced(root.right);}}//深度优先遍历树public int Bfs(TreeNode root) {if (root null) {return 0;}//返回最深节点的深度return Math.max(Bfs(root.left), Bfs(root.right)) 1;}
} 官方解法
方法二自底向上的递归
方法一由于是自顶向下递归因此对于同一个节点函数 height 会被重复调用导致时间复杂度较高。如果使用自底向上的做法则对于每个节点函数 height 只会被调用一次。
自底向上递归的做法类似于后序遍历对于当前遍历到的节点先递归地判断其左右子树是否平衡再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的则返回其高度高度一定是非负整数否则返回 −1。如果存在一棵子树不平衡则整个二叉树一定不平衡。
class Solution {public boolean isBalanced(TreeNode root) {return height(root) 0;}public int height(TreeNode root) {if (root null) {return 0;}int leftHeight height(root.left);int rightHeight height(root.right);if (leftHeight -1 || rightHeight -1 || Math.abs(leftHeight - rightHeight) 1) {return -1;} else {return Math.max(leftHeight, rightHeight) 1;}}
}
复杂度分析
时间复杂度
O(n)其中 n 是二叉树中的节点个数。使用自底向上的递归每个节点的计算高度和判断是否平衡都只需要处理一次最坏情况下需要遍历二叉树中的所有节点因此时间复杂度是 O(n)。
空间复杂度
O(n)其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数递归调用的层数不会超过 n。 官方解法部分
作者力扣官方题解 链接https://leetcode.cn/problems/balanced-binary-tree/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
