Question

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).

For example: Given binary tree [3,9,20,null,null,15,7],

3    / \   9  20
/  \    15   7

return its bottom-up level order traversal as:

[ [15,7], [9,20], [3] ]

Thinking:

  • Method 1:BFS
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) return result;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> res = new ArrayList<>();
            for(int i = 0; i < len; i++){
                TreeNode temp = queue.poll();
                res.add(temp.val);
                if(temp.left != null) queue.add(temp.left);
                if(temp.right != null) queue.add(temp.right);
            }
            result.add(res);
        }
        List<List<Integer>> finalRes = new ArrayList<>();
        for(int i = result.size() - 1; i >= 0; i--)
            finalRes.add(result.get(i));
        return finalRes;
    }
}

二刷

  1. 使用双端队列（在Java中的实现就是LinkedList）。 
    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 public List<List<Integer>> levelOrderBottom(TreeNode root) {
     LinkedList<List<Integer>> result = new LinkedList<>();
     if(root == null) return result;
     LinkedList<TreeNode> q = new LinkedList<>();
     q.add(root);
     while(!q.isEmpty()){
         int size = q.size();
         List<Integer> temp = new LinkedList<>();
         TreeNode node = null;
         for(int i = 0; i < size; i++){
             node = q.poll();
             temp.add(node.val);
             if(node.left != null) q.add(node.left);
             if(node.right != null) q.add(node.right);
         }
         result.addFirst(temp);
     }
     return result;
 }
}