Ming
0%

LeetCode-145

Posted on Edited on In

题目

结果

代码

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> path = new LinkedList<>();
        dfs(path, root);
        return path;
    }

    private void dfs(List<Integer> path, TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(path, root.left);
        dfs(path, root.right);
        path.add(root.val);
    }
}

迭代

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
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> path = new LinkedList<>();
        if (root == null) {
            return path;
        }

        Deque<TreeNode> stack = new LinkedList<>();
        // dejavu的作用是判断右子树是否遍历过
        TreeNode dejavu = null;
        while (root != null || !stack.isEmpty()) {
            // 左子树
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            // 回溯
            root = stack.pop();
            // 操作
            if (root.right == null || root.right == dejavu) {
                path.add(root.val);
                dejavu = root;
                // 将root置为null是为了跳过添加左子树的环节
                root = null;
            } else { // 右子树
                stack.push(root);
                root = root.right;
            }
        }
        return path;
    }
}

复杂度

时间复杂度：O（n），遍历每个节点

空间复杂度：O（n），栈的开销