Leetcode.103.Binary Tree Zigzag

题目

给定一个树, 按层输出节点值到一个二维数组, 第一层从左到右, 第二层从右到左, 依此类推.

Input: [3,9,20,null,null,15,7]
            3
           / \
          9  20
            /  \
           15   7
Output: [[3],[20,9],[15,7]]
Input: [1,2,3,4,null,null,5]
            1
           / \
          2   3
         /     \
        4       5
Output: [[1],[3,2],[4,5]]

思路

循环, 使用queue来存储下次需要打印的节点.
关于奇数层倒序, 可以通过stack来存储或者使用reverse函数. 貌似reverse函数效率挺高的.

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> res;
    int level = 0;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = (int)q.size();
        vector<int> vec;

        for (int i = 0; i < size; i++) {
            TreeNode *node = q.front();
            q.pop();
            if (node ==  nullptr) continue;
            vec.push_back(node->val);
            q.push(node->left);
            q.push(node->right);
        }

        if (vec.size() > 0) {
            if (level % 2 == 1) {
                reverse(vec.begin(), vec.end());
            }
            res.push_back(vec);
        }
        level++;
    }

    return res;
}

总结

了解queue在存储节点的过程, 第1次存储1个节点, 第2次存储2个节点, 第n次存储2²个节点.