Why {3,1,#,#,2} expect false???


  • 0
    W

    If I understand correctly, {3,1,#,#,2} should represent a tree as shown below (# means NULL), right?

              3
            /    \
          1       2
        /   \    /  \
       #     #  #    #
    

    obviously, this is a perfectly balanced tree. but why leetcode expecting false?

    This is my code:

    class Solution {
    public:
    
        bool isBalanced(TreeNode *root, int d, int& D) {
            if (root==NULL) {
                if(D!=-1) {
                    return abs(d-D)<=1;
                }
                D=d;
                return true;
            }
            return isBalanced(root->left, d+1, D) && isBalanced(root->right, d+1, D);
        }
        
        bool isBalanced(TreeNode *root) {
            int maxD = -1;
            return isBalanced(root, -1, maxD);
        }
    };
    
    
    
    Input:	{3,1,#,#,2}
    Output:	true
    Expected:	false

  • 1
    H

    I think {3,1,#,#,2} should be

            3 
           /   \
         1      #
       /    \
     #      2

  • 0
    W

    could you elaborate a little bit more? According to http://articles.leetcode.com/2010/09/serializationdeserialization-of-binary.html

    we serialize the tree with pre-order traversal, right?

    print 3, go to 3's left tree; {3}

    print 1, go to 1's left tree; {3, 1}

    print null, go to 1's right tree; {3, 1, #}

    print null, go to 3's right tree; {3, 1, #, #}

    print 2, end; {3, 1, #, #, 2}


  • 0
    H

    Well I think it traverses by level, you can go to Problem "Binary Tree Inorder Traversal " and see the explanation of OJ's Binary Tree Serialization.


Log in to reply
 

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