首页 > 代码库 > [leetcode] Binary Tree Zigzag Level Order Traversal

[leetcode] Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes‘ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3   /   9  20    /     15   7

return its zigzag level order traversal as:

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

思路:

BFS的基础题目。

题解:

技术分享
/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {        vector<vector<int> > res;        vector<int> tmp;        queue<TreeNode *> q;        bool flag = true;        int count = 0, num = 1;        if(root==NULL)            return res;        q.push(root);        while(!q.empty()) {            count = 0;            for(int i=0;i<num;i++) {                root = q.front();                q.pop();                tmp.push_back(root->val);                if(root->left) {                    q.push(root->left);                    count++;                }                if(root->right) {                    q.push(root->right);                    count++;                }            }            num = count;            if(!flag)                reverse(tmp.begin(), tmp.end());            flag = !flag;            res.push_back(tmp);            tmp.clear();        }        return res;    }};
View Code

 

[leetcode] Binary Tree Zigzag Level Order Traversal