Q:
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:
Given the following tree
[3,9,20,null,null,15,7]
:3 / \ 9 20 / \ 15 7
Return true.
Example 2:
Example 2:
Given the following tree
[1,2,2,3,3,null,null,4,4]
:1 / \ 2 2 / \ 3 3 / \ 4 4
Return false.
A:
Mistakes:/** * 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 isBalanced(TreeNode* root) { int l=0; return helper(root, l); } private: bool helper(TreeNode* root, int &depth) { if(!root) { depth = 0; return true; } int l=0, r = 0; bool isLeft = helper(root->left, l); bool isRight = helper(root->right, r); depth = 1+ max(l, r); return isLeft && isRight && abs(l-r)<=1; } };
Learned:
---------------------Java, 因为不能引用传值, ---------如果不平衡,就返回负 的树的高度
public class BalancedBinaryTree { public boolean isBalanced(TreeNode root) { return getHeight(root) >= 0 ; } private int getHeight(TreeNode root) { // get the weight, but if tree is unbalanced, return -1 if (root == null) return 0; int left = getHeight(root.left); int right = getHeight(root.right); if (Math.abs(left - right) > 1 || left < 0 || right < 0) return -1; return 1 + Math.max(left, right); } }
No comments:
Post a Comment