Two Iteration in Java: Preorder Traversal and Level Traversal


  • 0
    1. Level Traversal is very easy to understand
    public class Solution {
        public int maxDepth(TreeNode root) {
        	if (root == null) return 0;
        	
        	Queue<TreeNode> q = new LinkedList<TreeNode>();
        	q.add(root);
        	int count = 0;
        	
        	while (!q.isEmpty()) {
        		int size = q.size();
        		while (size-- > 0) {
        			TreeNode cur = q.poll();
        			if (cur.left != null) q.add(cur.left);
        			if (cur.right != null) q.add(cur.right);
        		}
        		count++;
        	}
        	
        	return count;
        }
    
    }
    
    
    1. Preorder Traversal is little bit of tricky: only after we visit right child can we delete this node from stack. That's why we need to use an extra pointer pre
    
    public class Solution {
        public int maxDepth(TreeNode root) {
            if(root == null) return 0;
            int max = 0;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            TreeNode pre = null;
            while(!stack.isEmpty() || cur!=null){
                while(cur!=null){
                    stack.push(cur);
                    cur = cur.left;
                }
                max = Math.max(max, stack.size());
                cur = stack.peek();
                if(cur.right == null || cur.right == pre){
                    pre = stack.pop();
                    cur = null;
                }else{
                    cur = cur.right;
                }
            }
            
            return max;
        }
    }
    
    

Log in to reply
 

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