Does anyone have an iterative accepted solution?


  • 0
    K

    Below is the straight forward recursive solution, does any one have the iterative implementation for the same?

    public class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer>list = new ArrayList<Integer>();
            return recursion(root, list);
        }
        public List<Integer> recursion(TreeNode root, List<Integer> list){
            if(root!=null){
                list.add(root.val);
                recursion(root.left,list);
                recursion(root.right,list);
            }else{
                return list;
            }
            
            return list;
        }
    }

  • 6
    E

    Simply, using recursion means that you are using call stack and your mutable state and order of execution are kept there. So if you should not use recursion, in other words, call stack -- get your own stack. You need to push items to the stack in such a way that when popped out the order will be correct. Thus I push right branch before left.

    public class Solution
    {
    	public List<Integer> preorderTraversal(TreeNode root)
    	{
    		LinkedList<Integer> integers = new LinkedList<>();
    		Stack<TreeNode> stack = new Stack<>();
    
    		// start with the root of the tree even if it is null
    		stack.push(root);
    
    		while (!stack.empty())
    		{
    			TreeNode n = stack.pop();
    			if (n != null)
    			{
    				integers.add(n.val);
    				stack.push(n.right);
    				stack.push(n.left);
    			}
    		}
    
    		return integers;
    
    	}
    }
    

  • 0
    K

    Thanks...nice solution.


  • 0
    E

    Stay on this track and may the force be with you! :)


  • 0
    N

    Here is my solution.

    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        for (Stack<TreeNode> toVisit = new Stack<>(); root != null; root = root.left != null ? root.left : toVisit.isEmpty() ?  null : toVisit.pop()) {
            res.add(root.val);
            if (root.right != null) toVisit.push(root.right);
        }
        return res;
    }
    

    It's a bit silly and definitely abuses the spirit of a for loop, but otherwise, it simply uses a Stack like every other iterative solution. Perhaps the only noteworthy aspect is that this avoids pushing the left nodes onto the stack since, if a left node exists, we can just go to it directly.


  • 0
    Y

    very smart.........simple


Log in to reply
 

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