前序遍历

中序遍历

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }

  • 时间复杂度：O(n)
    其中 n为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次

  • 空间复杂度：O(n)
    空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(root != null ||!stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;

        }
        return res;
    }

  • 时间复杂度：O(n)
    其中 n为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次

  • 空间复杂度：O(n)
    空间复杂度取决于递归的栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n) 的级别

Morris

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
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        TreeNode predecessor = null;

        while (root != null) {
            if (root.left != null) {
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }
                
                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {
                    res.add(root.val);
                    predecessor.right = null;
                    root = root.right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }
  • 时间复杂度：O(n)，每个节点会被访问两次，总时间复杂度为O(2n)
  • 空间复杂度：O(1)

颜色标记法

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
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    if(root == null){
        return list;
    }
    
    Stack<Object> stack=new Stack<>();
    stack.push(root);

    while(!stack.isEmpty()){
        Object obj = stack.pop();
        //第一次出栈
        if(obj instanceof TreeNode){
            TreeNode node=(TreeNode) obj;
            if(node.right!=null){
                stack.push(node.right);
            }
            stack.push(node.val);
            if(node.left!=null){
                stack.push(node.left);
            }
        }
        //第二次出栈
        else{
            list.add((Integer) obj);
        }
    }

    return list;
}

后序遍历