【题解】—— LeetCode一周小结7-阿里云开发者社区

上接：【题解】—— LeetCode一周小结6

12.二叉树的后序遍历

题目链接：145. 二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[3,2,1]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

提示：

树中节点的数目在范围 [0, 100] 内

-100 <= Node.val <= 100

进阶：递归算法很简单，你可以通过迭代算法完成吗？

题解：

方法一：递归遍历

先递归左子树，接着递归右子树，再访问根节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.*;
class Solution {
    private List<Integer> ans = new ArrayList<>(); // 用于存放后序遍历结果的列表
    /**
     * 执行后序遍历，返回遍历结果列表。
     * @param root 二叉树的根节点
     * @return 后序遍历结果列表
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        dfs(root); // 调用深度优先搜索函数进行后序遍历
        return ans; // 返回后序遍历结果列表
    }
    /**
     * 深度优先搜索函数，递归遍历二叉树，并将节点值存入结果列表。
     * @param root 当前处理的节点
     */
    private void dfs(TreeNode root) {
        if (root == null) { // 递归终止条件：当前节点为空
            return;
        }
        dfs(root.left); // 递归遍历左子树
        dfs(root.right); // 递归遍历右子树
        ans.add(root.val); // 将当前节点值加入结果列表（在递归后面加入）
    }
}

方法二：栈实现非递归遍历

在这个后序遍历的实现中，使用了一个额外的辅助栈和一个变量 prev 来记录上一个访问过的节点。算法的核心思想是在访问每个节点时，先判断其右子节点是否被访问过，如果右子节点未被访问过，则先遍历右子树；如果右子节点已被访问过或不存在，则将当前节点的值加入结果列表，并将其弹出栈，并更新 prev 为当前节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.*;
class Solution {
    /**
     * 执行后序遍历，返回遍历结果列表。
     * @param root 二叉树的根节点
     * @return 后序遍历结果列表
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>(); // 用于存放后序遍历结果的列表
        Deque<TreeNode> stk = new ArrayDeque<>(); // 辅助栈，用于遍历过程中保存节点
        TreeNode prev = null; // 用于记录上一个访问过的节点
        // 遍历二叉树
        while (root != null || !stk.isEmpty()) {
            if (root != null) {
                stk.push(root); // 将当前节点入栈
                root = root.left; // 移动到左子节点
            } else {
                TreeNode peekNode = stk.peek(); // 查看栈顶节点，但不出栈
                if (peekNode.right != null && peekNode.right != prev) { // 如果栈顶节点的右子节点存在且未被访问过
                    root = peekNode.right; // 移动到右子节点
                } else { // 如果栈顶节点的右子节点不存在或已被访问过
                    stk.pop(); // 栈顶节点出栈
                    ans.add(peekNode.val); // 将栈顶节点的值加入结果列表
                    prev = peekNode; // 更新上一个访问过的节点
                }
            }
        }
        return ans; // 返回后序遍历结果列表
    }
}

方法三：Morris 实现中序遍历

这段代码使用了 Morris 遍历的思想实现了二叉树的后序遍历，其时间复杂度为 O(n)，其中 n 是二叉树中的节点数。Morris 遍历算法的优点是空间复杂度为 O(1)，不需要额外的栈空间。在后序遍历中，需要额外的操作来将遍历路径上的节点逆序添加到结果列表中，这部分操作在 reverseAddNodes 方法中实现。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.*;
class Solution {
    /**
     * 执行 Morris 实现的后序遍历，返回遍历结果列表。
     * @param root 二叉树的根节点
     * @return 后序遍历结果列表
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>(); // 用于存放后序遍历结果的列表
        TreeNode dummy = new TreeNode(-1); // 添加一个虚拟节点作为辅助节点
        dummy.left = root; // 将虚拟节点的左子节点指向根节点
        TreeNode cur = dummy; // 初始化当前节点为虚拟节点
        // 遍历二叉树
        while (cur != null) {
            if (cur.left == null) { // 如果当前节点的左子节点为空
                cur = cur.right; // 移动到当前节点的右子节点
            } else { // 如果当前节点的左子节点不为空
                TreeNode prev = cur.left; // 找到当前节点的左子树的最右下角节点
                while (prev.right != null && prev.right != cur) {
                    prev = prev.right;
                }
                if (prev.right == null) { // 如果最右下角节点的右子节点为空
                    prev.right = cur; // 将最右下角节点的右子节点指向当前节点
                    cur = cur.left; // 移动到当前节点的左子节点
                } else { // 如果最右下角节点的右子节点不为空
                    reverseAddNodes(cur.left, prev, ans); // 将从当前节点的左子节点到 prev 节点这段路径上的节点，按照逆序添加到结果列表中
                    prev.right = null; // 恢复最右下角节点的右子节点为null
                    cur = cur.right; // 移动到当前节点的右子节点
                }
            }
        }
        return ans; // 返回后序遍历结果列表
    }
    /**
     * 将从 start 节点到 end 节点这段路径上的节点，按照逆序添加到结果列表中。
     * @param start 起始节点
     * @param end 终止节点
     * @param ans 结果列表
     */
    private void reverseAddNodes(TreeNode start, TreeNode end, List<Integer> ans) {
        reverseNodes(start, end); // 先翻转从 start 节点到 end 节点的路径上的节点
        TreeNode cur = end; // 初始化当前节点为 end 节点
        while (true) {
            ans.add(cur.val); // 将当前节点的值加入结果列表
            if (cur == start) { // 如果当前节点等于起始节点，结束循环
                break;
            }
            cur = cur.right; // 移动到当前节点的右子节点
        }
        reverseNodes(end, start); // 再次翻转从 start 节点到 end 节点的路径上的节点，恢复原状
    }
    /**
     * 翻转从 start 节点到 end 节点这段路径上的节点。
     * @param start 起始节点
     * @param end 终止节点
     */
    private void reverseNodes(TreeNode start, TreeNode end) {
        if (start == end) { // 如果起始节点等于终止节点，不需要翻转，直接返回
            return;
        }
        TreeNode x = start; // 初始化 x 节点为起始节点
        TreeNode y = start.right; // 初始化 y 节点为起始节点的右子节点
        while (true) {
            TreeNode z = y.right; // 初始化 z 节点为 y 节点的右子节点
            y.right = x; // 将 y 节点的右子节点指向 x 节点
            x = y; // 更新 x 节点为 y 节点
            y = z; // 更新 y 节点为 z 节点
            if (x == end) { // 如果 x 节点等于终止节点，结束循环
                break;
            }
        }
    }
}

13.二叉树的垂序遍历

题目链接：987. 二叉树的垂序遍历

给你二叉树的根结点 root ，请你设计算法计算二叉树的垂序遍历序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的垂序遍历从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的垂序遍历序列。

示例 1：

输入：root = [3,9,20,null,null,15,7]

输出：[[9],[3,15],[20],[7]]

解释：

列 -1 ：只有结点 9 在此列中。

列 0 ：只有结点 3 和 15 在此列中，按从上到下顺序。

列 1 ：只有结点 20 在此列中。

列 2 ：只有结点 7 在此列中。

示例 2：

输入：root = [1,2,3,4,5,6,7]

输出：[[4],[2],[1,5,6],[3],[7]]

解释：

列 -2 ：只有结点 4 在此列中。

列 -1 ：只有结点 2 在此列中。

列 0 ：结点 1 、5 和 6 都在此列中。

1 在上面，所以它出现在前面。

5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。

列 1 ：只有结点 3 在此列中。

列 2 ：只有结点 7 在此列中。

示例 3：

输入：root = [1,2,3,4,6,5,7]

输出：[[4],[2],[1,5,6],[3],[7]]

解释：这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。

因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

提示：

树中结点数目总数在范围 [1, 1000] 内

0 <= Node.val <= 1000

题解：

方法：深度优先DFS

这段代码实现了二叉树的垂直遍历，将节点按照列号分组存储，并在每组中按照行号和节点值进行排序。整体思路是使用深度优先搜索遍历二叉树，在遍历的过程中记录每个节点的行号、列号和值，并将其分组存储在 groups 中。最后，对每个分组按照题目要求的顺序进行排序，并构造出最终的结果列表。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 执行垂直遍历，返回按垂直顺序遍历的节点值列表。
     * @param root 二叉树的根节点
     * @return 垂直遍历结果列表
     */
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        // 使用 TreeMap 来保存分组，以确保按列顺序遍历
        Map<Integer, List<int[]>> groups = new TreeMap<>();
        
        // 执行深度优先搜索，记录节点的行号、列号和值
        dfs(root, 0, 0, groups);
        // 构造结果列表
        List<List<Integer>> ans = new ArrayList<>(groups.size());
        for (List<int[]> g : groups.values()) {
            // 对于同一列的节点，按照行号和值进行排序
            g.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
            List<Integer> vals = new ArrayList<>(g.size());
            // 将排序后的节点值加入结果列表
            for (int[] p : g) {
                vals.add(p[1]);
            }
            ans.add(vals);
        }
        return ans;
    }
    /**
     * 深度优先搜索函数，递归遍历二叉树，并记录节点的行号、列号和值。
     * @param node 当前处理的节点
     * @param row 当前节点的行号
     * @param col 当前节点的列号
     * @param groups 保存分组结果的映射表
     */
    private void dfs(TreeNode node, int row, int col, Map<Integer, List<int[]>> groups) {
        if (node == null) {
            return;
        }
        // 将当前节点加入对应列的分组中
        groups.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, node.val});
        // 递归处理左右子节点，更新行号和列号
        dfs(node.left, row + 1, col - 1, groups);
        dfs(node.right, row + 1, col + 1, groups);
    }
}

方法二：在 DFS 的同时记录 col的最小值，这样无需对 key 排序，也无需使用有序字典。

使用了 minCol 变量来记录最小的列号，而不是直接从 0 开始遍历 groups 映射表。这个变量的作用是确保我们的列号是从最小列号开始的，这样我们可以保证结果列表中的列是按照从左到右的顺序排列的。

具体区别在于以下几点：

使用 minCol 变量：我们初始化 minCol 为 0，并在遍历节点的过程中更新它。这样可以确保我们的列号是从最小列号开始的，而不是直接从 0 开始。这样做的好处是确保结果列表中的列是按照从左到右的顺序排列的。
构造结果列表时的列号遍历：在构造结果列表时，我们使用 minCol 变量作为起始列号，并以 minCol + groups.size() 作为结束列号。这样可以确保我们遍历到了所有的列号，并保证了结果列表中的列是按照从左到右的顺序排列的。

class Solution {
    private int minCol; // 用于记录最小列号
    /**
     * 执行垂直遍历，返回按垂直顺序遍历的节点值列表。
     * @param root 二叉树的根节点
     * @return 垂直遍历结果列表
     */
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, List<int[]>> groups = new HashMap<>(); // 用于保存分组结果的映射表
        dfs(root, 0, 0, groups); // 执行深度优先搜索遍历二叉树
        List<List<Integer>> ans = new ArrayList<>(groups.size());
        // 遍历每个分组，按照列号顺序构造结果列表
        for (int col = minCol; col < minCol + groups.size(); col++) {
            List<int[]> g = groups.get(col);
            g.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); // 对每个分组进行排序
            List<Integer> vals = new ArrayList<>(g.size());
            // 将排序后的节点值加入结果列表
            for (int[] p : g) {
                vals.add(p[1]);
            }
            ans.add(vals);
        }
        return ans; // 返回垂直遍历结果列表
    }
    /**
     * 深度优先搜索函数，递归遍历二叉树，并记录节点的行号、列号和值。
     * @param node 当前处理的节点
     * @param row 当前节点的行号
     * @param col 当前节点的列号
     * @param groups 保存分组结果的映射表
     */
    private void dfs(TreeNode node, int row, int col, Map<Integer, List<int[]>> groups) {
        if (node == null) {
            return;
        }
        minCol = Math.min(minCol, col); // 更新最小列号
        groups.computeIfAbsent(col, k -> new ArrayList<>()).add(new int[]{row, node.val}); // 将当前节点加入对应列的分组中
        // 递归处理左右子节点，更新行号和列号
        dfs(node.left, row + 1, col - 1, groups);
        dfs(node.right, row + 1, col + 1, groups);
    }
}

方法三：双数组

这段代码实现了二叉树的垂直遍历，并将节点按照列号分组存储在 left 和 right 中，一个列表 left 负责统计负数 col，另一个列表 right负责统计非负数 col。

然后将分组中的节点按照行号和节点值排序，最后将排序后的节点值添加到结果列表中。

整体思路是使用深度优先搜索遍历二叉树，在遍历的过程中将节点分组存储，并按照要求进行排序和组装结果列表。

相当于用两个列表来模拟双端队列。

class Solution {
    /**
     * 执行垂直遍历，返回按垂直顺序遍历的节点值列表。
     * @param root 二叉树的根节点
     * @return 垂直遍历结果列表
     */
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<int[]>> left = new ArrayList<>(); // 左侧分组列表
        List<List<int[]>> right = new ArrayList<>(); // 右侧分组列表
        dfs(root, 0, 0, left, right); // 执行深度优先搜索遍历二叉树，生成左右分组列表
        List<List<Integer>> ans = new ArrayList<>(left.size() + right.size()); // 结果列表
        Collections.reverse(left); // 反转左侧分组列表，使列号从小到大排序
        add(ans, left); // 添加左侧分组到结果列表
        add(ans, right); // 添加右侧分组到结果列表
        return ans; // 返回垂直遍历结果列表
    }
    /**
     * 深度优先搜索函数，递归遍历二叉树，并记录节点的行号、列号和值。
     * @param node 当前处理的节点
     * @param row 当前节点的行号
     * @param col 当前节点的列号
     * @param left 左侧分组列表
     * @param right 右侧分组列表
     */
    private void dfs(TreeNode node, int row, int col, List<List<int[]>> left, List<List<int[]>> right) {
        if (node == null) {
            return;
        }
        // 根据节点的列号确定分组，将节点添加到对应的分组中
        if (col < -left.size()) {
            left.add(new ArrayList<>());
        } else if (col == right.size()) {
            right.add(new ArrayList<>());
        }
        (col < 0 ? left.get(-col - 1) : right.get(col)).add(new int[]{row, node.val});
        // 递归处理左右子节点，更新行号和列号
        dfs(node.left, row + 1, col - 1, left, right);
        dfs(node.right, row + 1, col + 1, left, right);
    }
    /**
     * 将分组列表中的节点值添加到结果列表中。
     * @param ans 结果列表
     * @param a 分组列表
     */
    private void add(List<List<Integer>> ans, List<List<int[]>> a) {
        for (List<int[]> g : a) {
            Collections.sort(g, (p, q) -> p[0] != q[0] ? p[0] - q[0] : p[1] - q[1]); // 对分组中的节点按行号和值进行排序
            List<Integer> vals = new ArrayList<>(g.size());
            for (int[] p : g) {
                vals.add(p[1]); // 将排序后的节点值添加到结果列表
            }
            ans.add(vals); // 将结果列表加入到结果列表中
        }
    }
}

方法四：单数组

把所有 (col,row,val) 全部丢到同一个列表中，排序后按照 col分组。

class Solution {
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<int[]> data = new ArrayList<>();
        dfs(root, 0, 0, data);
        List<List<Integer>> ans = new ArrayList<>();
        data.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] != b[1] ? a[1] - b[1] : a[2] - b[2]);
        int lastCol = Integer.MIN_VALUE;
        for (int[] d : data) {
            if (d[0] != lastCol) {
                lastCol = d[0];
                ans.add(new ArrayList<>());
            }
            ans.get(ans.size() - 1).add(d[2]);
        }
        return ans;
    }
    private void dfs(TreeNode node, int row, int col, List<int[]> data) {
        if (node == null) {
            return;
        }
        data.add(new int[]{col, row, node.val});
        dfs(node.left, row + 1, col - 1, data);
        dfs(node.right, row + 1, col + 1, data);
    }
}

14.二叉树的层序遍历

题目链接：102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]

输出：[[1]]

示例 3：

输入：root = []

输出：[]

提示：

树中节点数目在范围 [0, 2000] 内

-1000 <= Node.val <= 1000

题解：

方法：迭代

广度优先遍历是按层层推进的方式，遍历每一层的节点。题目要求的是返回每一层的节点值，所以这题用广度优先来做非常合适。

广度优先需要用队列作为辅助结构，我们先将根节点放到队列中，然后不断遍历队列。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.*; 
class Solution {
  public List<List<Integer>> levelOrder(TreeNode root) {
    if(root==null) {
      return new ArrayList<List<Integer>>();
    }
    
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    //将根节点放入队列中，然后不断遍历队列
    queue.add(root);
    while(queue.size()>0) {
      //获取当前队列的长度，这个长度相当于 当前这一层的节点个数
      int size = queue.size();
      ArrayList<Integer> tmp = new ArrayList<Integer>();
      //将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中
      //如果节点的左/右子树不为空，也放入队列中
      for(int i=0;i<size;++i) {
        TreeNode t = queue.remove();
        tmp.add(t.val);
        if(t.left!=null) {
          queue.add(t.left);
        }
        if(t.right!=null) {
          queue.add(t.right);
        }
      }
      //将临时list加入最终返回结果中
      res.add(tmp);
    }
    return res;
  }
}

方法：递归

import java.util.*; 
class Solution {
  public List<List<Integer>> levelOrder(TreeNode root) {
    if(root==null) {
      return new ArrayList<List<Integer>>();
    }
    //用来存放最终结果
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    dfs(1,root,res);
    return res;
  }
  
  void dfs(int index,TreeNode root, List<List<Integer>> res) {
    //假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
    if(res.size()<index) {
      res.add(new ArrayList<Integer>());
    }
    //将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
    //res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
    res.get(index-1).add(root.val);
    //递归的处理左子树，右子树，同时将层数index+1
    if(root.left!=null) {
      dfs(index+1, root.left, res);
    }
    if(root.right!=null) {
      dfs(index+1, root.right, res);
    }
  }
}

15.二叉树的层序遍历 II

题目链接：107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值自底向上的层序遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

输入：root = [3,9,20,null,null,15,7]

输出：[[15,7],[9,20],[3]]

示例 2：

输入：root = [1]

输出：[[1]]

示例 3：

输入：root = []

输出：[]

提示：

树中节点数目在范围 [0, 2000] 内

-1000 <= Node.val <= 1000

题解：

方法：BFS

BFS遍历比较直观，就是按层遍历

我们将我们一层遍历得到的结果放到一个数组中，等这一层遍历完后，将这个数组放入到最终结果集res中。

因为题目要求是反序输出，所以我们只需将res翻转一下就可以了。

如上图，首先创建一个队列，将根节点root放入队列中，然后不断循环遍历这个队列。

对于树的第一层，其长度为1，而此时根节点也放到队列中了，所以队列的长度也是1，我们取出一个元素，将其放入临时数组中。

如果这个节点的左右孩子不为空，则将他们也放入队列中。

上图是处理第二层的过程，类似于第一层，由于第一层遍历完后，队列里有两个元素了，所以第二次遍历的时候，可以确定队列长度是2，于是执行两次，将2和3取出，放入临时数组中，之后再将2和3的两个孩子也放入队列中。

处理第三层时，队列长度就是4了，于是取出4个元素，再次处理。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null) {
            return new ArrayList<List<Integer>>();
        }
        //用来存放最终结果
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        //创建一个队列，将根节点放入其中
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            //每次遍历的数量为队列的长度
            int size = queue.size();
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            //将这一层的元素全部取出，放入到临时数组中，如果节点的左右孩子不为空，继续放入队列
            for(int i=0;i<size;++i) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left!=null) {
                    queue.offer(node.left);
                }
                if(node.right!=null) {
                    queue.offer(node.right);
                }
            }
            res.add(tmp);
        }
        //翻转最终结果并返回
        Collections.reverse(res);
        return res;
    }
}

方法：BFS 2

第一种方式中，我们将最终结果集定义成数组，等所有元素都放置完后，再翻转一下数组。

我们可以将其结构改成链表，以后每层遍历完将结果放入到链表的第一位，这样就自动完成了翻转的功能了。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null) {
            return new ArrayList<List<Integer>>();
        }
        //改用链表实现，每次都插入到第一位
        LinkedList<List<Integer>> res = new LinkedList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            for(int i=0;i<size;++i) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left!=null) {
                    queue.offer(node.left);
                }
                if(node.right!=null) {
                    queue.offer(node.right);
                }
            }
            //每次都保存到链表的第一位，这样自带了翻转的功能
            res.add(0,tmp);
        }
        return res;
    }
}

方法：DFS

DFS实现就不那么直观了，我们可以把二叉树结构改变一下，想象成一个三角形的结构

我们在递归遍历时，将第一层的元素放入到第一层的数组中，将第二层的的元素放入到第二层，第三层的元素放入第三层。

第三层的4是在5之前被遍历的，所以放入到第三层数组时，4就在5前面，同理6是在7前面被遍历的，所以放入到第三层时6就在7前面。

这次我们不用创建队列了，直接在最终结果集res上操作，res是个二维数组，集合中嵌套集合，但现在没有任何嵌套的集合。

如上图所示，一开始res是空的，当遍历到第一层时候，我们创建一个集合，放入res，然后将第一层的1，放到res[0]中。

遍历到第二层时，再创建一个集合放入res，然后将2放入res[1]中。

遍历到第三层时，同样再创建一个集合放入res，将4放入res[2]中。

当我们再回到第三层，遍历到5时，就不用再创建新集合了，直接将5放到到res[2]中即可。

之后，再将3放到res[1]，6、7放入res[2]中。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if(root==null) {
            return new ArrayList<List<Integer>>();
        }
        //用来存放最终结果
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(root,res,1);
        Collections.reverse(res);
        return res;
    }
    private void dfs(TreeNode root,ArrayList<List<Integer>> res,int index) {
        if(root==null) {
            return;
        }
        //如果index大于res大小，说明这一层没有对应的集合，需要新创建
        if(index>res.size()) {
            res.add(new ArrayList<Integer>());
        }
        //将当前层的元素直接放到对应层的末尾即可
        res.get(index-1).add(root.val);
        //继续遍历左右节点，同时将层高+1
        dfs(root.left,res,index+1);
        dfs(root.right,res,index+1);
    }
}

16.二叉树的锯齿形层序遍历

题目链接：103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]

输出：[[1]]

示例 3：

输入：root = []

输出：[]

提示：

树中节点数目在范围 [0, 2000] 内

-100 <= Node.val <= 100

题解：

方法：BFS

二叉树的BFS打印，就是一层一层的往下打印，因为这题要求的是先从左边，下一层从右边，在下一次从左边……左右交替的。我们可以使用一个变量leftToRight，如果是true就表示从左边开始打印，否则就从右边开始打印。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        //创建队列，保存节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);//先把节点加入到队列中
        boolean leftToRight = true;//第一步先从左边开始打印
        while (!queue.isEmpty()) {
            //记录每层节点的值
            List<Integer> level = new ArrayList<>();
            //统计这一层有多少个节点
            int count = queue.size();
            //遍历这一层的所有节点，把他们全部从队列中移出来，顺便
            //把他们的值加入到集合level中，接着再把他们的子节点（如果有）
            //加入到队列中
            for (int i = 0; i < count; i++) {
                //poll移除队列头部元素（队列在头部移除，尾部添加）
                TreeNode node = queue.poll();
                //判断是从左往右打印还是从右往左打印。
                if (leftToRight) {
                    //如果从左边打印，直接把访问的节点值加入到列表level的末尾即可
                    level.add(node.val);
                } else {
                    //如果是从右边开始打印，每次要把访问的节点值
                    //加入到列表的最前面
                    level.add(0, node.val);
                }
                //左右子节点如果不为空会被加入到队列中
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            //把这一层的节点值加入到集合res中
            res.add(level);
            //改变下次访问的方向
            leftToRight = !leftToRight;
        }
        return res;
    }
}

方法：DFS

这题除了使用BFS以外，还可以使用DFS，但这里要有个判断，如果走到下一层的时候集合没有创建，要先创建下一层的集合。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        travel(root, res, 0);
        return res;
    }
    private void travel(TreeNode cur, List<List<Integer>> res, int level) {
        if (cur == null)
            return;
        //如果res.size() <= level说明下一层的集合还没创建，所以要先创建下一层的集合
        if (res.size() <= level) {
            List<Integer> newLevel = new LinkedList<>();
            res.add(newLevel);
        }
        //遍历到第几层我们就操作第几层的数据
        List<Integer> list = res.get(level);
        //这里默认根节点是第0层，偶数层相当于从左往右遍历，
        // 所以要添加到集合的末尾，如果是奇数层相当于从右往左遍历，
        // 要把数据添加到集合的开头
        if (level % 2 == 0)
            list.add(cur.val);
        else
            list.add(0, cur.val);
        //分别遍历左右两个子节点，到下一层了，所以层数要加1
        travel(cur.left, res, level + 1);
        travel(cur.right, res, level + 1);
    }
}

17.N 叉树的层序遍历

题目链接：429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]

输出：[[1],[3,2,4],[5,6]]

示例 2：

输入：root =

[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

树的高度不会超过 1000

树的节点总数在 [0, 10^4] 之间

题解：树的（层序）遍历运用题

方法：BFS

我们需要以「层」为单位构建答案，因此在单次 BFS 过程中也按层进行。

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<>();
        Deque<Node> d = new ArrayDeque<>();
        if (root != null) d.addLast(root);
        while (!d.isEmpty()) {
            int size = d.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                Node t = d.pollFirst();
                for (Node node : t.children) d.addLast(node);
                list.add(t.val);
            }
            ans.add(list);
        }
        return ans;
    }
}

18.N 叉树的前序遍历

题目链接：589. N 叉树的前序遍历

给定一个 n 叉树的根节点 root ，返回其节点值的前序遍历。

n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]

输出：[1,3,5,6,2,4]

示例 2：

输入：root =

[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

提示：

节点总数在范围 [0, 10⁴]内

0 <= Node.val <= 10⁴

n 叉树的高度小于或等于 1000

题解：

方法：递归

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        dfs(root);
        return ans;
    }
    void dfs(Node root) {
        if (root == null) return ;
        ans.add(root.val);
        for (Node node : root.children) dfs(node);
    }
}

方法：迭代

使用栈模拟递归过程。

迭代过程中记录 (node = 当前节点, cnt = 当前节点遍历过的子节点数量) 二元组，每次取出栈顶元素，如果当前节点是首次出队（当前遍历过的子节点数量为 cnt=0），则将当前节点的值加入答案，然后更新当前元素遍历过的子节点数量，并重新入队，即将 (node,cnt+1)入队，以及将下一子节点 (node.children[cnt],0) 进行首次入队。

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        Deque<Object[]> d = new ArrayDeque<>();
        d.addLast(new Object[]{root, 0});
        while (!d.isEmpty()) {
            Object[] poll = d.pollLast();
            Node t = (Node)poll[0]; Integer cnt = (Integer)poll[1];
            if (t == null) continue;
            if (cnt == 0) ans.add(t.val);
            if (cnt < t.children.size()) {
                d.addLast(new Object[]{t, cnt + 1});
                d.addLast(new Object[]{t.children.get(cnt), 0});
            }
        }
        return ans;
    }
}

方法：通用递归转迭代

这是直接模拟系统执行递归的过程，这是一种更为通用的做法。在迭代过程中记录当前栈帧位置状态 loc，在每个状态流转节点做相应操作。

由于现代编译器已经做了很多关于递归的优化，现在这种技巧已经无须掌握。

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        Deque<Object[]> d = new ArrayDeque<>();
        d.addLast(new Object[]{0, root});
        while (!d.isEmpty()) {
            Object[] poll = d.pollLast();
            Integer loc = (Integer)poll[0]; Node t = (Node)poll[1];
            if (t == null) continue;
            if (loc == 0) {
                ans.add(t.val);
                d.addLast(new Object[]{1, t});
            } else if (loc == 1) {
                int n = t.children.size();
                for (int i = n - 1; i >= 0; i--) {
                    d.addLast(new Object[]{0, t.children.get(i)});
                }
            }
        }
        return ans;
    }
}

下接：【题解】—— LeetCode一周小结8

【题解】—— LeetCode一周小结7

12.二叉树的后序遍历

13.二叉树的垂序遍历

14.二叉树的层序遍历

15.二叉树的层序遍历 II

16.二叉树的锯齿形层序遍历

17.N 叉树的层序遍历

18.N 叉树的前序遍历

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【题解】—— LeetCode一周小结7

12.二叉树的后序遍历

13.二叉树的垂序遍历

14.二叉树的层序遍历

15.二叉树的层序遍历 II

16.二叉树的锯齿形层序遍历

17.N 叉树的层序遍历

18.N 叉树的前序遍历

热门文章

最新文章

相关电子书