题目描述

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]
]

解法一

思路

这题就是简单的二叉树层次遍历。想要收集自底向上的遍历结果，只需要在自顶向下每次层次遍历完成时将此层的遍历结果插入到结果list的最前面就好了，即result_list.insert(0, level_list)。

Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        queue = collections.deque()
        result = []
        queue.append(root)
        while queue:
            size = len(queue)
            current_list = []
            for i in range(0, size):
                node = queue.popleft()
                if node:
                    current_list.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)
            if current_list:
                result.insert(0, current_list)
        return result

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> currentList = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.remove();
                if (node != null) {
                    currentList.add(node.val);
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }
            if (!currentList.isEmpty()) {
                result.add(0, currentList);
            }
        }
        return result;
    }
}

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode *root) {
        queue<TreeNode *> que;
        vector<vector<int>> result;
        que.push(root);
        while (!que.empty()) {
            vector<int> currentList;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode *node = que.front();
                que.pop();
                if (node != nullptr) {
                    currentList.push_back(node->val);
                    que.push(node->left);
                    que.push(node->right);
                }
            }
            if (!currentList.empty()) {
                result.insert(result.begin(), currentList);
            }
        }
        return result;
    }
};