Input:{1,2,2,3,#,#,3,4,#,#,4} Output: true Expected:false what's wrong with my codes?


  • 0
    X
    class Solution {
        public:
            bool isBalanced(TreeNode *root) {                                                                                                              
                vector<int> v;
                _depth(root, 1, v); 
                if (v.size() > 0) {
                    if (v.size() == 1)
                        return v[0] - 1 > 1 ? false : true;
                    else {
                        int max = INT_MIN;
                        int min = INT_MAX;
                        for (int i = 0; i < v.size(); i++) {
                            max = v[i] > max ? v[i] : max;
                            min = v[i] < min ? v[i] : min;
                        }   
                        return max - min > 1 ? false : true;
                    }   
                }   
                return true;
            }   
            void _depth(TreeNode *p, int depth, vector<int> &v) {
                if (p) {
                    if (!p->left && !p->right) {
                        v.push_back(depth);
                    }   
                    _depth(p->left, depth+1, v); 
                    _depth(p->right, depth+1, v); 
                }   
            }   
    };

  • 0
    J

    I have the same question. After I draw the tree of {1,2,2,3,#,#,3,4,#,#,4}, I found it's like a triangle:
    1
    2--2
    3----3
    4------4
    In that way, I think it should be the balanced. What's wrong with that? Why is the result expected to be false?


  • 0
    M

    "For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1."

    The two subtrees of each child of the root (the 2s) have depths 2 and 0, and vice versa. Therefore, it is not balanced.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.