Ad

How To Reset The Global Variable Prev?

- 1 answer

This is the C solution for Leetcode 114. Flatten Binary Tree to Linked List

struct TreeNode* prev = NULL;

void flatten(struct TreeNode* root){
    if (root == NULL){
        return;
    }
    flatten(root->right);
    flatten(root->left);
    root->right = prev;
    root->left = NULL;
    prev = root;
}

When tested with

[1,2,5,3,4,null,6]
[0]

It would have this error output

[1,null,2,null,3,null,4,null,5,null,6]
[0,null,1,null,2,null,3,null,4,null,5,null,6]

The correct output should be

[1,null,2,null,3,null,4,null,5,null,6]
[0]

But if tested individually, both cases can pass, this is because the prev is a global variable.So how to reset this value?

Ad

Answer

Here is an iterative solution, if you'd be interested:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


void flatten(struct TreeNode* root) {
    struct TreeNode* lr;

    while (root != NULL) {
        if (root->left != NULL) {
            lr = root->left;

            while (lr->right != NULL) {
                lr = lr->right;
            }

            lr->right = root->right;
            root->right = root->left;
            root->left = NULL;
        }

        root = root->right;
    }
}

And here is LeetCode's recursive solution in Java with comments:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private TreeNode flattenTree(TreeNode node) {
        
        // Handle the null scenario
        if (node == null) {
            return null;
        }
            
        // For a leaf node, we simply return the
        // node as is.
        if (node.left == null && node.right == null) {
            return node;
        }
        
        //Recursively flatten the left subtree
        TreeNode leftTail = this.flattenTree(node.left);
        
        // Recursively flatten the right subtree
        TreeNode rightTail = this.flattenTree(node.right);
        
        // If there was a left subtree, we shuffle the connections
        // around so that there is nothing on the left side
        // anymore.
        if (leftTail != null) {
            leftTail.right = node.right;
            node.right = node.left;
            node.left = null;
        }
        
        // We need to return the "rightmost" node after we are
        // done wiring the new connections. 
        return rightTail == null ? leftTail : rightTail;
    }
    
    public void flatten(TreeNode root) {
        
        this.flattenTree(root);
    }
}

References

  • For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis1, 2 in there.
Ad
source: stackoverflow.com
Ad