A very simple C++ solution accepted in 12 ms


  • 1
    E

    The idea is pretty simple, like most questions in linked list, use a pre node. Each time visiting a new node, add it as the right child of pre node. The only issue is you should always use the original children in the DFS iteration.

    class Solution {
    private:
    	TreeNode * pre; 
    
    	void preOrder(TreeNode *root){
    		if(!root) return;
    
    		TreeNode *left = nullptr, *right = nullptr;  //record the original children 
    		if(root->left)
    			left = root->left;
    		if(root->right)
    			right = root->right; 
    		pre->right = root; 
    		pre = pre->right;
    
    		root->left = nullptr; //otherwise runtime error might occur
    		
            preOrder(left);
    		preOrder(right);
    	
    
    }
    public:
       void flatten(TreeNode *root) {
        	
        	pre = new TreeNode(-1);
    
        	preOrder(root);
    
            
    }
    

    };


  • 0
    L

    what is the wrong with the following code?

    void flatten(TreeNode *root) {
        if (!root) return;
        static TreeNode *pre = new TreeNode (-1);
        TreeNode *left, *right;
        left = root->left ? root->left : NULL;
        right = root->right ? root->right : NULL;
        
        pre->right = root;
        pre = pre->right;
        root->left = NULL;
        
        flatten(left);
        flatten(right); 
    }

  • 0
    E

    try to declare pre as a global variable instead of static


  • 0
    L

    why static doesn't work? It is global and will only be defined once. Each time, the recursion func is called, the origin value is preserved and modified in the recursion, right?


  • 0
    E

    u can check this discussion first:

    https://oj.leetcode.com/discuss/5800/different-answer-between-local-idle-and-leetcode?show=5800#q5800

    it seems like leetcode online judger would instance bunches of objects from one class simultaneously to run all the test cases at once. Therefore static variables would rise some errors.


  • 0
    K

    What is the meaning of pre=new TreeNode(-1) and why are we doing root->left=NULL?


  • 0
    E

    @kanv, pre=new TreeNode(-1) is to create a new treenode. if pre is an object instance rather other a pointer to treenode instance, there is no need to explicitly declare a new instance, which i think might be a better solution because of avoiding memory leakage.
    Also, without root->left = null, dead loop might occur.


Log in to reply
 

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