Has anyone solved this WITHOUT using a Hashmap for already visited nodes ?


  • 3
    R

    I've solved it using a stack and a hash map to keep track of already visited nodes so that I don't process them again and again. But it'd be nice to solve without the hash map so that I don't need O(n) space, Here's my code. Thanks

    {

    map<TreeNode*,bool> seenMap;
    stack<TreeNode*> s;
    vector<int> result;
    TreeNode* curr = root;
    
    if (root)
    	s.push(root);
    
    while (!s.empty())
    {
    	if (curr->left && (seenMap.find(curr->left) == seenMap.end()))
    	{
    		curr = curr->left;
    		s.push(curr);
    		continue;
    	}
    
    	else
    	{
    		curr = s.top();
    		s.pop();
    		result.push_back(curr->val);
    		seenMap[curr] = true;
    	}
    
    	if (curr->right && (seenMap.find(curr->right) == seenMap.end()))
    	{
    		curr = curr->right;
    		s.push(curr);
    	}
    }
    
    return result;
    

    }


  • 52
    M

    You actually are very close to the algorithm without using a map. You accurately go left as far as possible, and when you can't go left, you move right once. However, you failed to note that since you've traversed left as far as possible, and use the right child when no lefts remain before you pop the next element up the tree, when you pop an element, that means its left child must have already been fully expanded and does not need to be examined again.

    Therefore, instead of checking if you've seen it, just advance to the right children. Becuase the right child is only checked after the parent has been popped from the stack, so long as a node is only added once, no right child can have been expanded before.

    As you know the left child must have been visited already at the time of a pop, and the right child has not been, there is no need for a map as those states will always remain true.

    public ArrayList<Integer> inorderTraversal(TreeNode curr) {
        Stack<TreeNode> todo = new Stack<TreeNode>();
        ArrayList<Integer> res = new ArrayList<Integer>();
        while(!todo.isEmpty() || curr != null){
            if(curr != null){
                todo.add(curr);
                curr = curr.left;
            }
            else{
                curr = (TreeNode)todo.pop();
                res.add(new Integer(curr.val));
                curr = curr.right;
            }
        }
        return res;
    }

  • 0
    P

    public class Solution {

    ArrayList<Integer> ret = new ArrayList();
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
           if(root == null){
               return  ret;
           
           }
           // agreamos el nodo root, si solo si no hay left!!
           
           
           
         //entonces si el root left no es nulo, tenemos que entrar las veces necesarias
         if(root.left != null){
            
            inorderTraversal(root.left);
        }
        // si si es nulo, imprimios en donde esta esa linea
       
         ret.add(root.val);
        
          if(root.right != null){
            
            inorderTraversal(root.right);
        }  
            
         
          
     
     return ret; 
        
        
    }
    

    }

    Does this work?


  • 0
    M

    Yes and no. It will generate an inorder traversal, but the global variable will cause any future invocations to be added to the end, instead of being their own array. Secondly, the problem asks for an iterative solution, while the one you've presented is recursive.


  • 0
    Y

    Really great code


  • 0
    Y

    Java Version:

    public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
        TreeNode node = root;
        while(! stack.isEmpty() || node != null){
            if(node != null){
                stack.addFirst(node);
                node = node.left;
            }else{
                node = stack.removeFirst();
                result.add(node.val);
                node = node.right;
            }
            
        }
    
        return result;
    }
    

    }


  • 0
    P

    Thanks for sharing! However, I think your

    curr = root.left; should be curr = curr.left;

    isn't it?


  • 0
    M

    You're correct, yes. Thanks for pointing that out.


  • 0
    M
     public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root == null) return result;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode n = stack.pop();
            if(n.right != null){
                stack.push(n.right);
            }
            if(n.left == null) {
                result.add(n.val);
            }
            if(n.left!= null){
                TreeNode left = n.left;
                n.left = null;
                n.right = null;
                stack.push(n);
                stack.push(left);
            }
        }
        return result;
    }

  • 0
    S

    Thanks for your post. However it would be better to share solution with elaborating thoughts. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    S

    Thanks for your post. However it would be better to share solution with elaborating thoughts. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    M

    Thank you. I am sorry. I am a newbie here.


  • 0
    S

    Here's my solution, in C++. It's not as simple - maybe not as elegant - as @mike3's solution, but I think it does a little less work. Rather than always pop node then push val, I avoid pushing nodes that I won't have to come back to. I'm less working from the stack, and more working from a current node pointer with the stack of pointers to return to.

    vector<int> inorderTraversal( TreeNode *root ) {
        vector<int> r;
        if( NULL != root ) {
            vector<TreeNode *> p; p.push_back( NULL ); //list of parents seen but not heard
            while( NULL != root->left ) { p.push_back( root ); root = root->left; } //start with right subtree of leftmost child
            do { // for each right subtree
                r.push_back( root->val ); //add root val
                if( NULL != root->right ) {
                    root = root->right; //go to next right subtree
                    while( NULL != root->left ) { p.push_back( root ); root = root->left; } //then leftmost child (of subtree)
                }
                else{ root = p.back(); p.pop_back(); } //or to most recent "left-parent"
            } while( NULL != root ); //stop when no more right subtrees remain
        }
        return r;
    }
    

  • 0
    S
    This post is deleted!

  • 0
    H
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with elaborating thoughts. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info. Take a look at good sharing example


  • 0
    S

    The downside of this solution is that it ruins the tree structure.


  • 0
    L

    I am just wondering why not use Stack.push() and Stack.pop() methods?


  • 1
    R

    Here is my C++ version. Inorder Traversal means you visit left, then root, then right. So we need a stack to store the root node which we need to travel back after finishing its left tree.

    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode *root) {
            vector<int> result;
            vector<TreeNode *> stack;
            TreeNode *current = root;
            while(current != NULL || stack.size() != 0) {
            	while(current != NULL) {
            		stack.push_back(current);
            		current = current->left;
            	}
            	current = stack.back();
            	stack.pop_back();
            	result.push_back(current->val);
            	current = current->right;
            }
            return result;
        }
    };

  • 0
    T

    The best way I guess is not use Stack at all, here is my solution:
    It use Morris Traversal, Please take a looi at
    http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
    for the explain of the code.

    public class Solution {
    
    	private List<Integer> result = new ArrayList<Integer>();	
        public List<Integer> inorderTraversal(TreeNode root) {
        	if (root == null) return result;
        	TreeNode cur = root;
        	while (cur != null) {
        		if (cur.left == null) {
        			result.add(cur.val);
        			cur = cur.right;
        		}
        		else {
        			TreeNode pre = cur.left;
        			while (pre.right != null && pre.right != cur) 
        				pre = pre.right;
        			
        			if (pre.right == null) {
        				pre.right = cur;
        				cur = cur.left;
        			}
        			
        			else {
        				pre.right = null;
        				result.add(cur.val);
        				cur = cur.right;
        			}
        		}
        	}
        	
        	return result;
        }
    
    }

Log in to reply
 

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