Accepted Java Solution using queue instead of recursion


  • 1
    W
    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public int maxDepth(TreeNode root) {
            
            if(root == null)return 0;
            
            Queue<TreeNode> q = new Queue<TreeNode>();
            
            q.enQ(root);
            q.last = root;
            
            int depth = 0;
            
            while(q.count > 0){
                
                TreeNode p = q.deQ();
                if(p.left != null)q.enQ(p.left);
                if(p.right != null)q.enQ(p.right);
                
                if(q.last == p){
                    // current node is the last one on that depth
                    depth++;
                    if(q.tail != null)
                        q.last = q.tail.val;
                }
            }
            
            return depth;
            
        }
        
        public class Queue<T> {
            QueueNode<T> head = null, tail = null;
            T last = null;
            int count = 0;
            
            public void enQ(T t){
                
                QueueNode<T> n = new QueueNode<T>(t);
                
                if(this.count == 0){ // pay much attention to head & tail of Queue
                    this.tail = n;
                    this.head = n;
                    
                }else{
                    this.tail.next = n;
                    this.tail = n;
                }
                this.count++;
            }
            public T deQ(){
                
                if(this.count==0)return null;
                
                
                T tmp = this.head.val;
                
                if(head == tail){
                    // deQ last elem, reset head & tail
                    head = null;
                    tail = null;
                }else{
                    this.head = this.head.next;
                }
                
                this.count--;
                
                return tmp;
                
            }
            
        }
        
        public class QueueNode<T> {
            T val;
            QueueNode<T> next;
            public QueueNode(T t){
                this.val = t;
            }
        }
    }

  • 0
    D

    Why not use Java's Queue interface?


  • 0
    N

    You can use Deque interface as queue


Log in to reply
 

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