Solution 1: O(nlogn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // O(nlogn) class Solution { Solution 1: O(nlogn) public: bool isBalanced(TreeNode* root) { if(!root) return true; int left_height = height(root->left); int right_height = height(root->right); return (abs(left_height - right_height)<=1) && isBalanced(root->left) && isBalanced(root->right); } private: int height(TreeNode* root) { if(!root) return 0; return max(height(root->left), height(root->right))+1; } }; |
Solution 2: O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // O(n) class Solution { public: bool isBalanced(TreeNode* root) { if(!root) return true; bool balanced = true; height(root, &balanced); return balanced; } private: int height(TreeNode* root, bool* balanced) { if(!root) return 0; int left_height = height(root->left, balanced); if(!balanced) return -1; int right_height = height(root->right, balanced); if(!balanced) return -1; if(abs(left_height-right_height)>1) { *balanced = false; return -1; } return max(left_height, right_height) + 1; } }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 1 ms class Solution { private boolean balanced; private int height(TreeNode root) { if (root == null || !this.balanced) return -1; int l = height(root.left); int r = height(root.right); if (Math.abs(l - r) > 1) { this.balanced = false; return -1; } return Math.max(l, r) + 1; } public boolean isBalanced(TreeNode root) { this.balanced = true; height(root); return this.balanced; } } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
""" Author: Huahua Running time: 76 ms """ class Solution: def isBalanced(self, root): self.balanced = True def height(root): if not root or not self.balanced: return -1 l = height(root.left) r = height(root.right) if abs(l - r) > 1: self.balanced = False return -1 return max(l, r) + 1 height(root) return self.balanced |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment