Tree Treversal

Pre-order

Example

Given binary tree {1,#,2,3}:

    1
     \
      2
     /
    3

return [1,2,3].

Solution

public class Solution{
    // Way one: recursion and divide conquer
    public List<Integer> preorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        res.add(root.val);
        res.addAll(preorder(root.left));
        res.addAll(preorder(root.right));
        return res;
    }

    // Way two: stack
    public List<Integer> preorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;

        Stack<TreeNode> stack = new Stack<>();
        while(root != null) {
            res.add(root.val);
            stack.push(root);
            root = root.left;
        }
        while(!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            TreeNode extend = pop.right;
            while(extend != null){
                res.add(extend.val);
                stack.push(extend);
                extend = extend.left;
            }
        }
        return res;
    }

    // Way Three: concise and stack
    public List<Integer> preorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            res.add(pop.val);
            if(pop.right != null)
                stack.push(pop.right);
            if(pop.left != null)
                stack.push(pop.left);
        }
        return res;
    }
}

In-order

Example

Given binary tree {1,#,2,3}:

    1
     \
      2
     /
    3

return [1,3,2].

Solution

public class Solution{
    // Way one: recursion and divide conquer
    public List<Integer> inorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        res.addAll(inorder(root.left));
        res.add(root.val);
        res.addAll(inorder(root.right));
        return res;
    }

    // Way two: stack
    public List<Integer> inorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;

        Stack<TreeNode> stack = new Stack<>();
        do{
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            if(root.right != null)
                root = root.right;
            else
                root = null;
        }while(!stack.isEmpty() || root != null);
        // NOTE the loop should be continue to do when root is not null

        return res;
    }
}

Post-order

Example

Given binary tree {1,#,2,3}:

    1
     \
      2
     /
    3

return [3,2,1].

Solution

public class Solution{
    // Way one: recursion and divide conquer
    public List<Integer> postorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        res.addAll(postorder(root.left));
        res.addAll(postorder(root.right));
        res.add(root.val);
        return res;
    }

    // Way two: stack
    public List<Integer> inorder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;

        Stack<TreeNode> stack = new Stack<>();
        do{ 
            // tricky part 1: push the right child (if exist) first then push the root
            while(root != null) {
                if(root.right != null)
                    stack.push(root.right);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            // check if the right child exist and didn't be traveled
            if(!stack.isEmpty() && root.right != null && root.right == stack.peek()) {
                // swap the root and right child
                stack.pop();
                stack.push(root);
                root = root.right;
            }else {
                res.add(root.val);
                root = null;
            }
        }while(!stack.isEmpty());

        return res;
    }
}

Level Order

Example

Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution

public class Solution {
    /**
     * One queue
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // write your code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int cur = 1;
        int next = 0;
        ArrayList<Integer> row = new ArrayList<>();
        while(!queue.isEmpty()) {
            TreeNode node = queue.remove();
            cur--;
            row.add(node.val);
            if(node.left!=null) {
                queue.offer(node.left);
                next++;
            }
            if(node.right!=null) {
                queue.offer(node.right);
                next++;
            }

            if(cur == 0) {
                cur = next;
                next = 0;
                res.add(new ArrayList<>(row));
                row = new ArrayList<>();
            }
        }
        return res;
    }


    /**
     * Use DFS algorithm
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // write your code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        DFSUtil(res, 0, root);
        return res;
    }

    private void DFSUtil(ArrayList<ArrayList<Integer>> res, int level, TreeNode cur) {
        if(cur == null)
            return;
        if(level >= res.size()) {
            ArrayList<Integer> line = new ArrayList<>();
            line.add(cur.val);
            res.add(line);
        }else{
            ArrayList<Integer> line = res.get(level);
            line.add(cur.val);
            res.set(level, line);
        }
        DFSUtil(res, level + 1, cur.left);
        DFSUtil(res, level + 1, cur.right);
    }
}