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

例如:
给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

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

# 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 levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res = []
        num = []
        tmp1 = [root]
        tmp2 = []
        while len(tmp1) != 0 or len(tmp2) != 0:
            # tmp1为空，tmp2不为空
            if len(tmp1) == 0:
                tmp1 = copy.copy(tmp2)
                tmp2 = []
                res.append(num)
                num = []
            p = tmp1.pop(0)
            num.append(p.val)
            if p.left:
                tmp2.append(p.left)
            if p.right:
                tmp2.append(p.right)
        res.append(num)
        return res

/**
 * 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>> levelOrder(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.push_back(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.push_back(num);
        return res;
    }
};