【leetcode刷题】T119-二叉树的层次遍历 II

例如：
给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回其自底向上的层次遍历为：

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

# 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]]
        """
        if not root:
            return []
        res = []
        tmp = []
        ls1 = [root]
        ls2 = []
        while len(ls1) != 0 or len(ls2) != 0:
            if len(ls1) == 0:
                ls1 = copy.copy(ls2)
                ls2 = []
                res.append(tmp)
                tmp = []
            node = ls1.pop(0)
            tmp.append(node.val)
            if node.left:
                ls2.append(node.left)
            if node.right:
                ls2.append(node.right)
        res.append(tmp)
        return res[::-1]

/**
 * 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) {
        vector<vector<int>> res;
        if(!root)
            return res;
        vector<int> num;
        queue<TreeNode*> tmp1;
        tmp1.push(root);
        queue<TreeNode*> tmp2;
        TreeNode* p;
        while(!tmp1.empty() || !tmp2.empty()){
            // tmp1为空，tmp2不为空，则交换tmp1和tmp2
            if(tmp1.empty()){
                while(!tmp2.empty()){
                    tmp1.push(tmp2.front());
                    tmp2.pop();
                }
                res.insert(res.begin(), num);
                num.erase(num.begin(), num.end());
            }
            p = tmp1.front();
            tmp1.pop();
            num.push_back(p->val);
            if(p->left)
                tmp2.push(p->left);
            if(p->right)
                tmp2.push(p->right);
        }
        res.insert(res.begin(), num);
        return res;
    }
};