Accepted But My Solution destroys the Original Tree.


  • 0
    I
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> a;
        if(!root)
            return a;
            
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            TreeNode *t = s.top();
            if(t->right){
                TreeNode *temp= t->right;
                s.push(temp);
               
            }
            if(t->left){
            	TreeNode *temp = t->left;
                s.push(temp);
                
            }
            if(!t->left && !t->right){
                a.push_back(t->val);
                s.pop();
            }
             t->right = NULL;
             t->left = NULL;
        }
         return a;
    }
    

    May I know the solution that preserves the tree also. Thank you.


  • 1
    L

    L33tc0d3r wrote an article about it.


  • 0
    P

    I believe if we want to make sure the tree structure is preserved, we should not make change(e.g., reset the child pointers ) on the tree node in the code.


  • 6
    P
    class Solution {
    public:
    
        vector<int> postorderTraversal(TreeNode *root) {
            
            vector<int> res;
            if(root==NULL)
            return res;
            
            stack<TreeNode *> s;
            s.push(root);
            TreeNode * Lastprint=root;  //denote the last printed node;  update it when a node is printed
            
            while(!s.empty())
            {
                TreeNode *current=s.top();
               //if current is a leaf node, then print it
               //if all "current"'s children have been printed(last child is right child if there are two children.  
               //otherwise,left is the last child ), then print "current"
    
               if((current->left==NULL&¤t->right==NULL)||current->right==Lastprint||(current->left==Lastprint&¤t->right==NULL))
                {
                    res.push_back(current->val);   //time to print the current node
                    Lastprint=current;                 //update the last printed node
                    s.pop();
                }
                else 
                {
                    if(current->right!=NULL)
                    s.push(current->right);      //push the right child first and it will be printed later
                    if(current->left!=NULL)
                    s.push(current->left);       //then push the left child; but it will be printed earlier 
                }
            }
            
            return res;
        }
    };   

  • 0
    P

    This is my code but may not be optimal. Wish it would help you.


  • 0
    R
    This post is deleted!

  • 0
    R

    I keep two maps to keep track: leftChildVisitedMap and rightChildVisitedMap.
    When I push a node's left child to stack (or if the left child is null), I also add that node to leftChildVisitedMap (same for the right child). At the beginning of each iteration, I check the top element in the stack and if it's in both leftChildVisitedMap and rightChildVisitedMap, then I visit the node.
    This way you don't touch the original tree for the cost of keeping two additional hashmaps, hence O(2*n) space complexity


  • 6
    W

    My Java code:

    public class Solution {
        public ArrayList<Integer> postorderTraversal(TreeNode root) {
            ArrayList<Integer> result=new ArrayList<Integer>();
            if (root==null) return result;
            Stack <TreeNode> s=new Stack<TreeNode>();
            s.push(root);
            while (!s.empty()){
                TreeNode n=s.pop();
                if (n.right==null && n.left==null) result.add(n.val);
                else {
                    s.push(new TreeNode(n.val)); //a special node with no child
                    if (n.right!=null) s.push(n.right);
                    if (n.left!=null) s.push(n.left);
                }
            }
            return result;
        }
    }

  • 0
    J

    TreeNode *temp = t->left;
    s.push(temp);

    can just be changed to
    s.push(t->left);

    no need to use temp here


Log in to reply
 

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