Cannot find out BUG causing Runtime Error


  • 0
    R

    My idea is basically flatten binary tree recursively. with the flatten_helper function to flatten a sub-tree from root, and return this sub-tree's last node in flattened linked list.

    BUT, this causes RuntimeError with input {1, #, 2}, after walking through for a lot of times, i still cannot figure out why. Is there anyone can help and pick the bug out??

       void flatten(TreeNode *root) {
            if ( NULL==root ) { return; }
            flatten_helper(root);
        }
        
        TreeNode * flatten_helper(TreeNode * root){
        
            if ( NULL==root->left && NULL==root->right ){//Leaf Node last node is root
                return root;
            } else if ( NULL==root->left ){
                //root->right is already root->right
                TreeNode * right_last = flatten_helper(root->right);
                return right_last;
            } else if ( NULL==root->right ){
                TreeNode * left_last = flatten_helper(root->left);
                root->right = root->left;
                return left_last;
            } else {
                TreeNode * left_last = flatten_helper(root->left);
                TreeNode * right_last = flatten_helper(root->right);
                left_last->right = root->right;
                root->right = root->left;
                right_last->right = NULL;
                return right_last;
            }
        }

  • 2
    L

    The BUG here is not because of the result your code runs, it's because of the way the leetcode uses to check.
    the right answer may look like the following:

    void flatten(TreeNode *root) {
            if ( NULL==root ) { return; }
            flatten_helper(root);
        }
    
        TreeNode * flatten_helper(TreeNode * root){
    
            if ( NULL==root->left && NULL==root->right ){//Leaf Node last node is root
                return root;
            } else if ( NULL==root->left ){
                //root->right is already root->right
                TreeNode * right_last = flatten_helper(root->right);
                return right_last;
            } else if ( NULL==root->right ){
                TreeNode * left_last = flatten_helper(root->left);
                root->right = root->left;
                root->left = NULL;
                return left_last;
            } else {
                TreeNode * left_last = flatten_helper(root->left);
                TreeNode * right_last = flatten_helper(root->right);
                left_last->right = root->right;
                root->right = root->left;
                root->left = NULL;
                return right_last;
            }
        } 
    

    the only difference that from your code is I assign NULL to the left sub tree. And why does this work? I don't know. It's unnecessary to do that. But anyway, you have to assign Null to the left. That may not be a good design for an OJ, btw.


  • 0
    Y

    I met the same problem. But I finally found that I forgot to reset the node's left child to NULL,so the judge running in a circle and cause RE. You may check this.


  • 0
    T

    It works!Thank u!


  • 0

    Thank u very much!


Log in to reply
 

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