题目描述（简单难度）

树的层次遍历，和 的不同之处是，之前输出的数组顺序是从根部一层一层的输出，现在是从底部，一层一层的输出。

解法一 DFS

把 的贴过来看一下。

之前我们根据 level 得到数组的位置，然后添加。

  1. ans.get(level).add(root.val);
  3. ans    [] [] [] [] [].
  4. index  0  1  2  3  4
  5. level  0  1  2  3  4
  6.        ------------>
  7. index = 0 + level
  9. 现在 level 是逆过来存的
  10. ans    [] [] [] [] [].
  11. index  0  1  2  3  4
  12. level  4  3  2  1  0
  13.        <------------
  14. index = 4 - level
  16. 4 就是 ans 的末尾下标，就是 ans.size() - 1
  17. 所以代码变为
  18. ans.get(ans.size() - 1 - level).add(root.val);

此外还有句代码要改。

  1.     List<List<Integer>> ans = new ArrayList<>();
  2.     DFS(root, 0, ans);
  3.     return ans;
  6. private void DFS(TreeNode root, int level, List<List<Integer>> ans) {
  7.     if (root == null) {
  8.         return;
  9.     }
  10.     // 当前层数还没有元素，先 new 一个空的列表
  11.     if (ans.size() <= level) {
  12.         ans.add(0, new ArrayList<>());
  13.     }
  14.     // 当前值加入
  15.     ans.get(ans.size() - 1 - level).add(root.val);
  17.     DFS(root.left, level + 1, ans);
  18.     DFS(root.right, level + 1, ans);
  19. }

解法二 BFS

从根节点往下走的代码贴过来。

BFS相比于DFS要简单些，因为BFS是一次性把当前层的元素都添加到ans中，所以我们只需要改一句代码。

  1. ans.add(subList);

改成添加到头部即可。

再改个函数名字， 总体代码就是

  1. public List<List<Integer>> levelOrderBottom(TreeNode root) {
  3.     if (root == null)
  4.         return ans;
  5.     queue.offer(root);
  6.     while (!queue.isEmpty()) {
  7.         int levelNum = queue.size(); // 当前层元素的个数
  8.         List<Integer> subList = new LinkedList<Integer>();
  9.         for (int i = 0; i < levelNum; i++) {
  10.             TreeNode curNode = queue.poll();
  11.             if (curNode != null) {
  12.                 subList.add(curNode.val);
  13.                 queue.offer(curNode.left);
  14.                 queue.offer(curNode.right);
  15.             }
  16.         }
  17.         if (subList.size() > 0) {
  18.             ans.add(0, subList);
  19.         }
  20.     }
  21.     return ans;
  22. }

总

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情