题目描述（简单难度）

107. Binary Tree Level Order Traversal II - 图1

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

解法一 DFS

把 102 题 的DFS贴过来看一下。

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

之前我们根据 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. if(ans.size()<=level){
  2.     ans.add(new ArrayList<>());
  3. }
  4. 在添加当前 level 的第一个元素的时候，首先添加一个空列表到 ans 中
  5. 假设当前 level = 2，ans 中只添加了 level 是 0 和 1 的元素
  6. ans    [3] [9] 
  7. index   0   1  
  8. level   1   0  
  9. 因为 level 是从右往左增加的，所以空列表要到 ans 的头部
  10. ans     [] [3] [9] 
  11. index   0   1   2
  12. level   2   1   0  
  13. 所以代码改成下边的样子
  14.  ans.add(0，new ArrayList<>());

综上，只要改了这两处就可以了。

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

解法二 BFS

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

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

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

  1. ans.add(subList);

改成添加到头部即可。

  1. ans.add(0,subList);

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

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

总

这道题依旧考层次遍历，只需要在 102 题 的基础上，找到 level 和 index 的对应关系即可。此外，因为我们在头部添加元素，所以用链表会好一些。如果数组的话，还得整体后移才能添加新的元素。

windliang wechat

添加好友一起进步~

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

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