Clean Java Iterative Solution


  • 32
    M

    I do believe if you can think of an iterative solution, it's always better than using a recursive one. And technical y every recursive solution can be converted into a equivalent iterative one.

    public int maxDepth(TreeNode root) {
    	if (root == null)
    		return 0;
    	
    	Deque<TreeNode> stack = new LinkedList<TreeNode>();
    	
    	stack.push(root);
    	int count = 0;
    	
    	while (!stack.isEmpty()) {
    		int size = stack.size();
    		while (size-- > 0) {
    			TreeNode cur = stack.pop();
    			if (cur.left != null)
    				stack.addLast(cur.left);
    			if (cur.right != null)
    				stack.addLast(cur.right);
    		}
    		count++;
    
    	}
    	return count;
    
    }

  • 3
    J

    this is like BFS.


  • 1
    T

    This is like level order traversal


  • 0

    Well, actually, in Swift, DFS (recursion) is a little bit faster than BFS (iteration).


  • 0
    M
    This post is deleted!

  • 11
    D

    @mo10 This solution works and it is using BFS, but your stack implementation is a little confusing. This stack is used like a queue, as you do stack.addLast() and stack.pop() in a Last-In-Last-Out style. It would be better to use a real queue here.


  • 0
    G

    said in Clean Java Iterative Solution:

    It is not always better to have a iterative solution. Sure, it is more terse and readable. Languages that do not support tail call optimization (TCO) natively, like Java, pay a higher cost than iterative. I would suggest edit the text to say this.


  • 1
    N

    Thanks for the answer but rather then using stack as a queue, we can make our intentions more clearer by directly using queue. Here is an updated version

        public int maxDepth(TreeNode root) {
        if (root == null) return 0;
    
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 0;
    
        while (!queue.isEmpty()) {
          int size = queue.size();
          while (size-- > 0) {
            TreeNode node = queue.poll();
    
            if (node.left != null) {
              queue.offer(node.left);
            }
    
            if (node.right != null) {
              queue.offer(node.right);
            }
          }
          count++;
        }
    
        return count;
        }
    

  • 0
    J

    Your sol use BFS and you can use linkedlist instead deque.


Log in to reply
 

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