【算法/剑指Offer】请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

最新推荐文章于 2022-05-04 23:47:36 发布

HelloZEX

最新推荐文章于 2022-05-04 23:47:36 发布

阅读量1.6k

点赞数

分类专栏：算法

本文链接：https://blog.csdn.net/HelloZEX/article/details/81098307

版权

算法专栏收录该内容

43 篇文章

订阅专栏

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

可以用一个队列，一个栈实现
也可用两个栈实现，这里用两个栈实现，思路简单一点。
来个图直接解释，

链接：https://www.nowcoder.com/questionTerminal/91b69814117f4e8097390d107d2efbe0
来源：牛客网

vector<vector<int> > Print( TreeNode* pRoot)
    {
        vector<vector<int> > result;
        if( pRoot != NULL)
        {
            stack<TreeNode*> stack1, stack2;
            stack1.push( pRoot);
            while(!stack1.empty() || !stack2.empty() )
            {
                vector<int> ret1,ret2;
                TreeNode* cur = NULL;
                while( !stack1.empty())
                {
                  //偶数行放栈2
                    cur = stack1.top();
                    if( cur->left)
                        stack2.push(cur->left);
                    if(cur->right)
                        stack2.push(cur->right);
                    ret1.push_back(stack1.top()->val);  //保存奇数行数据
                    stack1.pop();
                }
                if(ret1.size())
                    result.push_back(ret1);
 
                while( !stack2.empty())
                {
                    //奇数行放栈1
                    cur = stack2.top();
                    if(cur->right)
                        stack1.push( cur->right);
                    if(cur->left)
                        stack1.push( cur->left);
 
                    ret2.push_back(stack2.top()->val); //保存偶数行数据
                    stack2.pop();
                }
                if(ret2.size())
                    result.push_back(ret2);
            }
 
        }
        return result;
    }