【力扣刷题】_二叉树的非递归遍历方法

发表于 | 分类于

二叉树的非递归遍历方法

前中后序遍历就是典型的DFS深度优先搜索，层序遍历就是典型的BFS广度优先搜索。

使用递归方法来对二叉树进行各种遍历的思路比较好想到，但是使用非递归的方法来对二叉树进行遍历很多时候需要巧思，不是一下子就能想出来的。

1.前序遍历

思路：

  • 将根节点入栈
  • 循环执行以下操作，直到栈为空：
    • 弹出栈顶元素，进行访问
    • 将top.right入栈
    • 将top.left入栈

2.中序遍历

思路：

  • 检查节点是否有左子树，有则先不访问该节点，先将该节点放入栈中，然后对其左子节点重复该步骤；
  • 找到最左边的叶子节点，访问该节点，然后弹出栈顶元素并访问，再查看该节点是否有右子节点，有则以此右子节点为起点重复第一步；无则继续弹出栈顶元素并访问，重复第二步，直到栈为空。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();

    //root还不是null或者栈中还有节点，则说明节点还没有遍历完毕。
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        ans.add(root.val);
        root = root.right;
    }

    return ans;
}

3.后序遍历

思路：

  • 将根节点入栈
  • 循环执行以下操作，直到栈为空：
    • 如果栈顶节点是叶子节点 或者 上一次访问的节点是栈顶节点的子节点，则弹出栈顶节点并访问；
    • 否则，将top.right和top.left按顺序入栈。

4.层序遍历

思路：

  • 将根节点入队列
  • 循环执行以下操作，直到队列为空
    • 将对头节点head出队并访问
    • 将head.left和head.right按顺序入栈

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();

    //考虑root为空的特殊情况。
    if (root == null) return ans;

    //java中常用LinkedList实现Deque。
    Deque<TreeNode> deque = new LinkedList<>();
    deque.offer(root);
    while (!deque.isEmpty()) {
        List<Integer> answer = new ArrayList<>();

        //计算每层的节点数量
        int levelLength = deque.size();
        for (int i = 0; i < levelLength; i++) {
            root = deque.poll();
            answer.add(root.val);
            if (root.left != null) deque.offer(root.left);
            if (root.right != null) deque.offer(root.right);
        }
        ans.add(answer);
    }
    return ans;
}