前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<Integer> res = new ArrayList<>();

        Deque<TreeNode> stack = new LinkedList<>();
        stack.addLast(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.removeLast();
            res.add(cur.val);
            //先遍历左子树，所以右子树先进栈
            if (cur.right != null) stack.addLast(cur.right);
            if (cur.left != null) stack.addLast(cur.left);
        }

        return res;
    }
}

中序遍历

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
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        //遍历顺序：左-根-右
        if (root == null) return new ArrayList<>();

        ArrayList<Integer> res = new ArrayList<>();
        TreeNode cur = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while (!stack.isEmpty() || cur != null) {
            //优先处理左子树
            while (cur != null) {
                stack.addLast(cur);
                cur = cur.left;
            }
            //此时左子树已处理（cur==null)，继续处理根节点
            cur = stack.removeLast();
            res.add(cur.val);
            //如果无右子节点，cur置null。否则cur指向右子树节点
            if (cur.right == null) {
                cur = null;
            } else {
                cur = cur.right;
            }
       }

        return res;
    }
}

后序遍历

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
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        //遍历顺序，左-右-根
        if (root == null) return new ArrayList<>();
        ArrayList<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode prev = null;   //前一个遍历的节点

        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.addLast(cur);
                cur = cur.left;
            }
            cur = stack.removeLast();   //此节点左子树为空
            if (cur.right == null || cur.right == prev) {
                //如果右子树也为空（或者右子树已遍历），则添加根节点值
                res.add(cur.val);
                prev = cur;
                cur = null;
            } else {
                //如果右子树不为空，或者未曾遍历，则优先处理右子树（将该节点继续入栈）
                stack.addLast(cur);
                cur = cur.right;
            }
        }

        return res;
    }
}