LeetCode Tree Traversal Summary

Posted on | In

Here I summarize the iterative implementation for preorder, inorder, and postorder traverse.

PreOrder model

1
2
3
4
5
6
7
8
public static void helper(List<Integer> res, TreeNode root){
	if(root == null)
		return ;
  	// 操作
  	// 终止条件
  	helper(res, root.left);
  	helper(res, root.right);
}

Inorder model

1
2
3
4
5
6
7
public static void helper(List<Integer> res, TreeNode root){
	if(root == null)
		return null;
	helper(res, root.left);
	// 操作
	helper(res, root.right);
}

144.Pre Order Traverse

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        return recursivePreTraversal(root, res);       
    }
    public List<Integer> recursivePreTraversal(TreeNode root, List<Integer> res){
        if(root!=null){
            res.add(root.val);
            recursivePreTraversal(root.left, res);
            recursivePreTraversal(root.right, res);
        }
        return res;
    }
}

Running time: O(n), 1ms

Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> res = new ArrayList<>();
        TreeNode node = root;
        while(node!=null || !stack.isEmpty()){
            // left
            while(node!=null){
                System.out.println(node.val);
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            // right subtree
            if(!stack.isEmpty()){
                node = stack.pop();
                node = node.right;
            }
        }
        return res;
    }
}

Running time: O(n), 10ms

Stack Right node first, then left node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            res.add(node.val);
            if(node.right!=null)
                stack.push(node.right); //first right node, 
            if(node.left!=null)
                stack.push(node.left);
        }
        return res;
    }
}

Running time: O(n), 2ms

94.In Order Traverse

Recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        return recursiveInTraversal(root, res);
    }
    public List<Integer> recursiveInTraversal(TreeNode root, List<Integer> res){
        if(root!=null){
            recursiveInTraversal(root.left, res);
            res.add(root.val);
            recursiveInTraversal(root.right, res);
        }
        return res;
    }
}

Running time: O(n), 1ms

Iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while(node!=null||!stack.isEmpty()){
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            if(!stack.isEmpty()){
                node = stack.pop();
                res.add(node.val);
                node = node.right;
            }
        }
        return res;
    }
}

Running time: O(n), 2ms

145.Post Order Traverse

Using addFirst(Element e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode p = root;
    while(!stack.isEmpty() || p != null) {
        if(p != null) {
            stack.push(p);
            result.addFirst(p.val);  // Reverse the process of preorder
            p = p.right;             // Reverse the process of preorder
        } else {
            TreeNode node = stack.pop();
            p = node.left;           // Reverse the process of preorder
        }
    }
    return result;
}

Using LastVisit node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<>();
        if(root == null)
            return res;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        TreeNode lastVisit = root;
        while(node != null || !stack.isEmpty()){
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            node = stack.peek();
            if(node.right==null || node.right==lastVisit){
                res.add(node.val);
                stack.pop();
                lastVisit = node;
                node = null;
            }
            else
                node = node.right;
        }
        return res;
    }
}

后序遍历在决定是否可以输出当前节点的值的时候，需要考虑其左右子树是否都已经遍历完成。

所以需要设置一个lastVisit游标。

若lastVisit等于当前考查节点的右子树，表示该节点的左右子树都已经遍历完成，则可以输出当前节点。

并把lastVisit节点设置成当前节点，将当前游标节点node设置为空，下一轮就可以访问栈顶元素。

102.Level Order Traversal

Iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left!=null)
                    queue.offer(node.left);
                if(node.right!=null)
                    queue.offer(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

Time complexity: O(n), 2ms

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        recursiveLevel(res, root, 1);
        return res;
    }
    public void recursiveLevel(List<List<Integer>> res, TreeNode node, int depth){
        if(node == null)
            return;
        if(res.size() == depth-1){
            List<Integer> temp1 = new ArrayList<>();
            temp1.add(node.val);
            res.add(temp1);
        }
        else if(res.size() >= depth){
            List<Integer> temp2 = res.get(depth-1);
            temp2.add(node.val);
        }
        recursiveLevel(res, node.left, depth+1);
        recursiveLevel(res, node.right, depth+1);        
    }
}

Time complexity: O(n), 1ms