[LeetCode]Binary Tree Level Order Traversal II,解题报告 - c++编程基础

题目

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

思路

题目不难，说是从底向上按层遍历二叉树，其实偷个懒，从上向下挨层遍历之后，然后对ArrayList里的元素来个逆序就OK了
从上向下挨层遍历二叉树，参考链接：java集合LinkeLlist模拟队列

ArrayList元素逆序，可以自己写个翻转的方法（双指针O(n)），也可以直接调用Collections类里的静态方法reverse

AC代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
     public ArrayList
  
   > levelOrderBottom(TreeNode root) {
        ArrayList
   
    > list = new ArrayList
    
     >(); LinkedList
     
       queue = new LinkedList
      
       (); TreeNode p; if (root == null) { return list; } queue.addLast(root); while (! queue.isEmpty()) { ArrayList
       
         sublist = new ArrayList
        
         (); LinkedList
         
           subqueue = new LinkedList
          
           (); while (! queue.isEmpty()) { p = queue.removeFirst(); sublist.add(p.val); if (p.left != null) { subqueue.addLast(p.left); } if (p.right != null) { subqueue.addLast(p.right); } } list.add(sublist); queue.addAll(subqueue); } Collections.reverse(list); return list; } }