[Leetcode] Binary tree Zigzag level order traversal二叉树Z形层次遍历

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},

return its zigzag level order traversal as:

[

  [3],

  [20,9],

  [15,7]

]

confused what"{1,#,2,3}"means? > read more on how binary tree is serialized on OJ.

OJ's Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

题目要求按Z字形以此输出每层，主体还是层次遍历。

思路一：只在Binary tree level order traversal的基础上增加对层数的奇偶的判断，然后依此来决定是否反转当前行即可；

/**

 * 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>> levelOrderBottom(TreeNode* root)

    {

        vector<vector<int>> res;

        queue<TreeNode *> Q;

        if(root)    Q.push(root);

        size_t level=;     //第level层，初始为第一层

        while( !Q.empty())

        {

            int count=;

            int levCount=Q.size();

            vector<int> levNode;

            while(count<levCount)

            {

                TreeNode *curNode=Q.front();

                Q.pop();

                levNode.push_back(curNode->val);

                if(curNode->left)

                    Q.push(curNode->left);

                if(curNode->right)

                    Q.push(curNode->right);

                count++;

            }

            if(level% ==)     //偶数层，反转levNode再压入res

                reverse(levNode.begin(),levNode.end());

            res.push_back(levNode);

            level++;

        }

        return res;

    }

};

思路二：

利用队列，在每一层结束时向栈中压入NULL，则遇到NULL就标志一层的结束，就可以存节点，分奇偶的选择性的反转当前层的节点。特别值得注意的是，循环到最后一行后，若是还压入NULL，会造成死循环，故在压人入NULL时要判断栈是否为空。这也是在

层次遍历为主题的基础上增加层反转条件即可。

/**

 * 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;

        queue<TreeNode *> Q;

        if(root==NULL)  return res;

        Q.push(root);

        Q.push(NULL);              //第一层的结束

        vector<int> levNode;       //存放每层的节点

        size_t level=;            //第level层，初始为第一层

        while( !Q.empty())

        {

            TreeNode *cur=Q.front();

            Q.pop();

            if(cur)

            {

                levNode.push_back(cur->val);    //必须在if内，因栈顶节点可能为NULL

                if(cur->left)

                    Q.push(cur->left);

                if(cur->right)

                    Q.push(cur->right);

            }

            else

            {

                if(level% ==)        //偶数层，反转levNode再压入res

                    reverse(levNode.begin(),levNode.end());

                res.push_back(levNode);

                level++;

                levNode.clear();

                if( !Q.empty())   //最后一行，不要压入

                    Q.push(NULL);

            }

        }

        return res;

    }

};

巴特西

[Leetcode] Binary tree Zigzag level order traversal二叉树Z形层次遍历

最新文章

热门文章