ZEXI JIN

outline:

1. pre-order, post-order, in-order traversal of binary tree
2. level-order traversal of binary tree

pre-order, post-order, in-order traversal of binary tree

pre-order:

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

post-order:

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }
    
    public void postorder(TreeNode node, List res) {
        if (node != null) {
            postorder(node.left, res);
            postorder(node.right, res);
            res.add(node.val);
        }
    }
}

in-order:

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }
    
    public void inorder(TreeNode node, List res) {
        if (node != null) {
            inorder(node.left, res);
            res.add(node.val);
            inorder(node.right, res);
        }
    }
}

level-order

recursive method:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int level = 0;
        if (root == null)
            return res;
        level_recur(root, res, level);
        return res;
    }
    
    public void level_recur(TreeNode node, List<List<Integer>> res, int level) {
        // add new level if necessary
        if (res.size() == level)
            res.add(new ArrayList<Integer>());      
        // add current value to corresponding level
        res.get(level).add(node.val);
        // recursion
        if (node.left != null)
            level_recur(node.left, res, level+1);
        if (node.right != null)
            level_recur(node.right, res, level+1);
    }
}

iterative method:

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null)
            return res;
        int level = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()) {
            res.add(new ArrayList<Integer>());
            int level_len = queue.size();
            for (int i = 0; i < level_len; i++) {
                TreeNode cur = queue.remove();
                res.get(level).add(cur.val);
                if (cur.left != null)
                    queue.add(cur.left);
                if (cur.right != null)
                    queue.add(cur.right);
            }
            level += 1;
        }
        return res;
    }
}