首页 > 代码库 > 【leetcode】Binary Tree Zigzag Level Order Traversal (middle)

【leetcode】Binary Tree Zigzag Level Order Traversal (middle)

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]]

 

思路:由于需要排成之字形,所以用一个栈来存储当前行的内容,另一个栈来存储下一行的内容。

以根为第0层,那么偶数层都应该从左向右输出。那么每次遇到偶数层,压入下一层奇数层时就按从左到右的顺序,这样弹栈时就是从右到左。

纠结了一会儿,AC了。

class Solution {public:    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {        vector<vector<int>> ans;        if(root == NULL)        {            return ans;        }        int level = 0; //记录当前层号        vector<TreeNode *> curlevel;        curlevel.push_back(root);        while(!curlevel.empty())        {            vector<int> partans;            vector<TreeNode *> nextlevel;            if(level % 2 == 0) //偶数层,根是第0层            {                while(!curlevel.empty()) //本层不为空                {                    if(curlevel.back()->left != NULL) //先压入左边,再压入右边                    {                        nextlevel.push_back(curlevel.back()->left);                    }                    if(curlevel.back()->right != NULL)                    {                        nextlevel.push_back(curlevel.back()->right);                    }                    partans.push_back(curlevel.back()->val);                    curlevel.pop_back();                }                ans.push_back(partans);                curlevel = nextlevel;            }            else            {                while(!curlevel.empty()) //本层不为空                {                    if(curlevel.back()->right != NULL) //先压入右边,再压入左边                    {                        nextlevel.push_back(curlevel.back()->right);                    }                    if(curlevel.back()->left != NULL)                     {                        nextlevel.push_back(curlevel.back()->left);                    }                    partans.push_back(curlevel.back()->val);                    curlevel.pop_back();                }                ans.push_back(partans);                curlevel = nextlevel;            }            level++;        }        return ans;    }    void createTree(TreeNode * &root)    {        int n;        cin >> n;        if(n != 0)        {            root = new TreeNode(n);            createTree(root->left);            createTree(root->right);        }    }};

 

看看别人的答案。思路不一样。

class Solution {vector<vector<int> > result;public:vector<vector<int> > zigzagLevelOrder(TreeNode *root) {    if(root!=NULL)    {        traverse(root, 0);    }    for(int i=1;i<result.size();i+=2)    {        vector<int>* v = &result[i];        std:reverse(v->begin(), v->end());    }    return result;}void traverse(TreeNode* node, int level){    if(node == NULL) return;    vector<int>* row = getRow(level);    row->push_back(node->val);    traverse(node->left, level+1);    traverse(node->right, level+1);}vector<int>* getRow(int level){    if(result.size()<=level)    {        vector<int> newRow;        result.push_back(newRow);    }    return &result[level];}};

 

【leetcode】Binary Tree Zigzag Level Order Traversal (middle)