题目

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：

给定二叉树 [3,9,20,null,null,15,7],
    3

   / \

  9  20

    /  \

   15   7
返回锯齿形层次遍历如下：
[

  [3],

  [20,9],

  [15,7]

]

考点

1.stack 双栈

2.tree

3.vector

思路

设置两个栈 ，分别用于存储不同层的子节点，存储的顺序和打印的顺序相反，所以用栈实现。

为什么用两个栈，不用一个栈，通过上图分析，如果只有一个栈，打印完3之后，把7、6push入栈后，无法将2弹出。

首先将根节点放入开口向左的栈stack1里。

然后开始循环，因为有可能这个二叉树只有一个根节点，所以关于子树的操作之前，都要判断是否存在子树，否则可能出现野指针。

用cur和next表示两个栈的序号。当前栈的元素为空时，就进行下一个栈的打印,cur=1-cur;next=1-next;。

结束条件:两个栈的元素都为空。

代码

newcoder

/*

struct TreeNode {

    int val;

    struct TreeNode *left;

    struct TreeNode *right;

    TreeNode(int x) :

            val(x), left(NULL), right(NULL) {

    }

};

*/

class Solution {

public:

    vector<vector<int> > Print(TreeNode* pRoot) {

        //定义容器

        vector<int> subret;

        vector<vector<int>> ret;

        //1.入口检查

        if(!pRoot)

            return ret;

        int cur = 1;

        int next = 0 ;

        //level[0]奇数级节点的栈，从左至右存储,level[1]偶数级节点的栈，从右至左存储,

        stack<TreeNode*> level[2];

        //level[0]:stack1,level[1]:stack2

        //将根节点放入stack2中

         level[1].push(pRoot);

        while(!level[0].empty()||!level[1].empty())

        {

            while(!level[cur].empty())

            {

                TreeNode* curNode=level[cur].top();

                subret.push_back(curNode->val);

                level[cur].pop();

                if(cur==0)//

                {

                    if(curNode->right)

                        level[next].push(curNode->right);

                    if(curNode->left)

                        level[next].push(curNode->left);

                }

                else

                {

                     if(curNode->left)

                        level[next].push(curNode->left); 

                    if(curNode->right)

                        level[next].push(curNode->right);

                }

            }

            if(level[cur].empty())

            {

                cur=1-cur;

                next=1-next;

                ret.push_back(subret);

                subret.clear();

            }

        }

        return ret;

    }

};

leetcode

/**

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

        //局部变量

        std::stack<TreeNode*> stack1;

        std::stack<TreeNode*> stack2;

        vector<vector<int>> ret;

        vector<int> temp;

        //鲁棒性检查

        if(!root)

            return ret;

        //栈1中放入根节点

        stack1.push(root);

        //如果两个栈中还有节点

        while(!stack1.empty()||!stack2.empty())

        {

            //栈2是空的就打印栈1

            if(stack2.empty())

            {

                while(!stack1.empty())

                {

                    ///记录当前node,temp，pop

                    TreeNode* cur=stack1.top();

                    temp.push_back(cur->val);

                    stack1.pop();

                    //注意左右顺序

                    if(cur->left)

                        stack2.push(cur->left);

                    if(cur->right)

                        stack2.push(cur->right);

                }

                //栈1打印完，push temp容器，清空temp，

                //开始打印栈2，操作和上面一样，只是左右顺序不同

                ret.push_back(temp);

                temp.clear();

            }

            else

            {

                if(stack1.empty())

                {

                    while(!stack2.empty())

                    {

                        TreeNode* cur=stack2.top();

                        temp.push_back(cur->val);

                        stack2.pop();

                        if(cur->right)

                            stack1.push(cur->right);

                        if(cur->left)

                            stack1.push(cur->left);

                    }

                    ret.push_back(temp);

                    temp.clear();

                }

            }

        }

        return ret;

    }

};

问题

1.vector

使用时，要#include<vector> ，也要using namespace std;

因为queue和stack都是单进单出，所以只有push(),没有push_back()

2.双栈和二叉树有对称的情况，所以第二种解法更好。

巴特西

32-3题：LeetCode103. Binary Tree Zigzag Level Order Traversal锯齿形层次遍历/之字形打印二叉树

题目

考点

思路

代码

问题

最新文章

热门文章