0. 题目

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

1. c++版本

方法1，其实就是借助层序遍历，将每层的内容存到vector中，注意要求是倒序排列

 vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        vector<int> tmp;
        queue<TreeNode *> fatherQueue, childQueue;
        if (root)
            fatherQueue.push(root);
        while(!fatherQueue.empty()) {
            root = fatherQueue.front();
            tmp.push_back(root->val);
            fatherQueue.pop();
            if (root->left)
                childQueue.push(root->left);
            if (root->right)
                childQueue.push(root->right);
            if (fatherQueue.empty() && !childQueue.empty()) {
                swap(fatherQueue, childQueue);
                result.insert(result.begin(),tmp);
                tmp.clear();
            }
        }
        if (!tmp.empty())
            result.insert(result.begin(),tmp);
        return result;
    }

方法2，使用一个queue，注意n=Queue.size(); i<n;, 每次插入之后Queue长度会实时变化，所以需要先将Queue.size()保存

 vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        queue<TreeNode *> Queue;
        if (root)
            Queue.push(root);

        while(!Queue.empty()) {
            vector<int> tmp;
            for(int i=0, n=Queue.size(); i<n; ++i){
                root = Queue.front();
                tmp.push_back(root->val);
                Queue.pop();
                if (root->left)
                    Queue.push(root->left);
                if (root->right)
                    Queue.push(root->right);
            }
           if (!tmp.empty())
                result.insert(result.begin(), tmp);  
        }
        return result;
    }

2. python版本

 def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        result = []
        q = Queue.deque()
        if root:
            q.append(root)
        while q:
            n = len(q)
            tmp = []
            for i in range(0, n):
                root = q[0]
                tmp.append(root.val)
                q.popleft()
                if root.left:
                    q.append(root.left)
                if root.right:
                    q.append(root.right)
            if tmp:
                result.insert(0, tmp)
        return  result