C++ one stack similar to preorder


  • 0
    N
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        void flatten(TreeNode* root) {
            if (root == NULL)
                return;
            stack<TreeNode* > righter;
            
            righter.push(root);
            
            TreeNode* lastNode = NULL;
            
            while(!righter.empty()) {
                TreeNode* tmp = righter.top();
                righter.pop();
                
                if (lastNode) {
                    lastNode->right = tmp;
                }
                if (tmp->right)
                    righter.push(tmp->right);
                
                lastNode = tmp;
                
                while(tmp->left) {
                    tmp->right = tmp->left;
                    tmp->left = NULL;
                    tmp = tmp->right;
                    
                    if (tmp->right)
                        righter.push(tmp->right);
                    
                    lastNode = tmp;
                }
            }
        }
    };
    

  • 0
    Q

    Check this out. Iterative without a stack<>
    https://discuss.leetcode.com/topic/60046/accepted-c-solution-6ms


Log in to reply
 

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