【LeetCode】升级打怪之路 Day 14：二叉树的遍历

今���题目：

• 144. 二叉树的前序遍历
• 94. 二叉树的中序遍历
• 145. 二叉树的后序遍历
• 102. 二叉树的层序遍历

  目录

  • • Problem 1：二叉树的递归遍历 【easy】
    • Problem 2：二叉树的迭代遍历 【classic】
    • • 2.1 前序遍历 迭代版
      • 2.2 中序遍历 迭代版
      • 2.3 后序遍历 迭代版 【必背】
      • Problem 3：二叉树的层次遍历 【easy】

        今天主要学习了二叉树的递归遍历、迭代遍历和层序遍历，其中递归遍历和层序遍历都很简单，而迭代遍历的代码写起来稍有困难，这部分需要在理解的基础上，把伪代码背过。

        Problem 1：二叉树的递归遍历 【easy】

        递归遍历二叉树很简单了，可以拿这三个遍历题练练手：

        • 144. 二叉树的前序遍历
        • 94. 二叉树的中序遍历
        • 145. 二叉树的后序遍历

          Problem 2：二叉树的迭代遍历 【classic】

          △ 第一次访问； ○ 第二次访问；☆ 第三次访问

          2.1 前序遍历 迭代版

          144. 二叉树的前序遍历

          伪代码思路：

          void preOrder2(TreeNode T) {    Stack S;    TreeNode p = T;    while (p !=null && !S.empty()) {        if (p) {            visit(p);       // 第一次经过时访问之            S.push(p);                  p = p.left();   // 一路向左        } else {            S.pop(p);            p = p.right();  // 向右走（step 10）        }    }}

          Java 代码实现：

          class Solution {    public List preorderTraversal(TreeNode root) {        if (root == null) {            return Collections.emptyList();        }                List stack = new ArrayList();        List result = new ArrayList();        TreeNode p = root;        while (p != null || !stack.isEmpty()) {            if (p != null) {                result.add(p.val);                stack.addLast(p);                p = p.left;            } else {                p = stack.removeLast();                p = p.right;            }        }        return result;    }}

          2.2 中序遍历 迭代版

          94. 二叉树的中序遍历

          伪代码如下：

          void inOrder2(TreeNode T) {    Stack S;    TreeNode p = T;  // p 是遍历指针        while (p != null || !S.empty()) {  // 栈不空或者 p 不空时循环        // 一路向左直到空节点       if (p) {           S.push(p);       // 当前节点入栈           p = p.left;      // 向左走       }       // 遇到空节点       else {           S.pop(p);        // 访问栈顶元素（step9），由于接下来要访问之，故 pop           visit(p);        // 访问之           p = p.right;     // 向右子树走（step10）       }    }}

          2.3 后序遍历 迭代版 【必背】

          145. 二叉树的后序遍历

          这个建议直接背过，掌握这个算法思路后，并不难背，大不了多写几遍代码。

          算法思路：① 一路向左走并入栈，直到空节点；② 碰到空节点后，读取栈顶元素但不弹出（step9）：如果存在右孩子并且未访问过（为了确定之前是从左孩子返回过来的），则向右走；否则，栈顶元素出栈并访问之。

          • 为了区分返回到一个节点时是从左子树回来的还是从右子树回来的，代码设定了辅助指针 recent，它指向最近访问过的节点，当 p.right != recent 时，表示这是从左子树回来的，还没有访问过右子树。

            后序遍历迭代版特点：

            • 当一个节点的左右子树都被访问后才能出栈（pop）。
            • 实际上，当访问一个节点 p 时，栈中节点恰好是 p 节点的所有祖先，从栈底到栈顶再加上 p 节点，刚好构成从根节点到 p 节点的一条路径。很多算法设计都利用了这一思想，比如求根到某节点的路径，求两个节点的最近公共祖先等。

              伪代码如下：

              void postOrder2(TreeNode T) {    Stack S;    TreeNode p = T, recent = null;    while (p != null && !S.empty()) {        if (p) {            S.push(p);            p = p.left;        } else {                // 向右            p = S.top();        // 读取栈顶节点            if (p.right && p.right != recent) { // 若存在右孩子，且未被访问过                p = p.right;    // 向右走            } else {            // 否则弹出节点并访问之                S.pop(p);                visit(p);                recent = p;     // 更新最近访问的节点                p = null;       // 节点访问完后，重置 p 指针            }        } // end else    } // end while}

              代码实现：

              class Solution {    public List postorderTraversal(TreeNode root) {        List stack = new ArrayList();        List result = new ArrayList();        TreeNode p = root, recent = null;        while (p != null || !stack.isEmpty()) {            if (p != null) {                stack.addLast(p);                p = p.left;            } else {                p = stack.getLast();                if (p.right != null && recent != p.right) {                    p = p.right;                } else {                    result.add(p.val);                    recent = p;                    stack.removeLast();                    p = null;                }            }        }        return result;    }}

              Problem 3：二叉树的层次遍历 【easy】

              102. 二叉树的层序遍历

              算法思想：

              1. 初始化一个辅助队列 Q；
              2. 根节点入队；
              3. 若 Q 非空，则队头节点出队并访问之，并将其左右孩子入队（如果有的话）；
              4. 重复 3 直至队空。

              伪代码实现：

              void levelOrder(BiTree T) {    Queue Q;        // 1. 初始化一个辅助队列    BiTree p;    Q.offer(T);      // 2. 根节点入队    while (!Q.empty()) {    // 3. 若 Q 非空，则        p = Q.poll();       // 队头节点出队并        visit(p);           // 访问之        // 并将其左右孩子入队（如果有的话）        if (p.left != null)  Q.offer(p.left);        if (p.right != null) Q.offer(p.right);        // 4. 重复 3 直至队空    }}