110. Balanced Binary Tree
Easy
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as:
a binary tree in which the left and right subtrees of every node differ in height by no more than 1.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: true
Example 2:
Input: root = [1,2,2,3,3,null,null,4,4] Output: false
Example 3:
Input: root = [] Output: true
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]
. -104 <= Node.val <= 104
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | //C++: method1 18ms /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isBalanced(TreeNode* root) { int len = 0; return dfs(root, len); } bool dfs(TreeNode* root, int &len){ if(!root) return true; len++; int len_left = 0, len_right = 0; if(!dfs(root->left, len_left)) return false; if(!dfs(root->right, len_right)) return false; if(abs(len_left-len_right)>1) return false; len += max(len_left, len_right); return true; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | /** * 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) { return helper(root)>=0; } int helper(TreeNode node){ if(node==null) return 0; int l = helper(node.left); if(l<0) return -1; int r = helper(node.right); if(r<0) return -1; if(Math.abs(r-l)>1) return -1; return Math.max(l, r)+1; } } |
No comments:
Post a Comment