重庆博达建设集团网站,潍坊企业网络推广,成都网站建设 lkcms,简单软件开发工具剑指 Offer 55 - II. 平衡二叉树
难度#xff1a;easy\color{Green}{easy}easy 题目描述
输入一棵二叉树的根节点#xff0c;判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1#xff0c;那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 […剑指 Offer 55 - II. 平衡二叉树
难度easy\color{Green}{easy}easy 题目描述
输入一棵二叉树的根节点判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7][3,9,20,null,null,15,7][3,9,20,null,null,15,7] 3/ \9 20/ \15 7返回 truetruetrue 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4][1,2,2,3,3,null,null,4,4][1,2,2,3,3,null,null,4,4] 1/ \2 2/ \3 3/ \4 4返回 falsefalsefalse 。
限制
0树的结点个数100000 树的结点个数 100000树的结点个数10000
注意本题与主站 110 题相同https://leetcode-cn.com/problems/balanced-binary-tree/ 算法
(递归)
递归判断
先递归判断两棵子树是否是平衡的递归的过程中记录每棵树的最大深度值然后判断两棵子树的最大深度的差是否不大于1。
复杂度分析 时间复杂度每个节点仅被遍历一次且判断的复杂度是 O(1)O(1)O(1)。所以总时间复杂度是O(n)O(n)O(n)。 空间复杂度 : O(n)O(n)O(n)
C 代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool ans;bool isBalanced(TreeNode* root) {ans true;dfs(root);return ans;}int dfs(TreeNode* root) {if (!root) return 0;int lh dfs(root-left), rh dfs(root-right);if (abs(lh - rh) 1) ans false;return max(lh, rh) 1;}
};算法2
构造一个获取当前子树的深度的函数 maxdepth(root) 通过比较某子树的左右子树的深度差 abs(maxdepth(root.left) - maxdepth(root.right)) 1 是否成立来判断某子树是否是二叉平衡树。若所有子树都平衡则此树平衡。
C 代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {if (!root) return 0;return max(maxDepth(root-left), maxDepth(root-right)) 1;}bool isBalanced(TreeNode* root) {if (!root) return true;int left maxDepth(root-left);int right maxDepth(root-right);return abs(left - right) 1 isBalanced(root-left) isBalanced(root-right);}
};
