Как сбросить глобальную переменную пред?

Question

Это решение C для Leetcode 114. Свести двоичное дерево в связанный список

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;
}

При тестировании с

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

Будет выведена эта ошибка

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

Правильный вывод должен быть

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

Но если тестировать индивидуально, оба случая могут пройти, потому что prev является глобальной переменной. Итак, как сбросить это значение?

Answer 1

Вот итеративное решение, если вам интересно:

/**
 * 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;
    }
}

А вот рекурсивное решение LeetCode в Java с комментариями:

/**
 * 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);
    }
}

Ссылки

• Дополнительные сведения см. На Доске обсуждения . Существует множество принятых решений с множеством языков и объяснений, эффективных алгоритмов, а также асимптотик c время / пространство анализ сложности ^{1 , 2} там.