剑指offer---按只字形顺序打印二叉树

class Solution
{
public:
    vector<vector<int> > Print(TreeNode* pRoot)
    {

        TreeNode* cur = pRoot;
        stack<TreeNode*> stack1_LeftToRight;
        stack<TreeNode*> stack2_RightToLeft;
        stack1_LeftToRight.push(pRoot);
        vector<vector<int> > result;
        if (pRoot == NULL)    return result;
        while ((!stack1_LeftToRight.empty()) || (!stack2_RightToLeft.empty()))
        {
            vector<int> re;
            if( (!stack1_LeftToRight.empty()) && (stack2_RightToLeft.empty()))
            {
                while (!stack1_LeftToRight.empty())
                {
                    TreeNode* cur= stack1_LeftToRight.top();
                    if(cur->left!=NULL) stack2_RightToLeft.push(cur->left);
                    if(cur->right!=NULL) stack2_RightToLeft.push(cur->right);
                    re.push_back(cur->val);
                    stack1_LeftToRight.pop();
                }
                result.push_back(re);
            }
            else
            {
                while (!stack2_RightToLeft.empty())
                {
                    TreeNode* cur = stack2_RightToLeft.top();
                    if(cur->right!=NULL) stack1_LeftToRight.push(cur->right);
                    if(cur->left!=NULL) stack1_LeftToRight.push(cur->left);
                    re.push_back(cur->val);
                    stack2_RightToLeft.pop();
                }
                result.push_back(re);
            }
            re.clear();
        }
        return result;

    }

};
时间: 07-31

剑指offer---按只字形顺序打印二叉树的相关文章

剑指offer 按之字形顺序打印二叉树

题目描述 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推. 思路: 1.有了之前层次遍历一行一行输出的经验,我们可以直接用一个变量记录行数,如果是奇数行,就将队列中的元素按顺序所有保存下来,如果是偶数行,就顺序保存到一个临时vector中,再逆序保存下来. 1 /* 2 struct TreeNode { 3 int val; 4 struct TreeNode *left; 5 struct Tre

剑指Offer——按之字形顺序打印二叉树

题目描述: 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推. 分析: 我们都知道二叉树的层次遍历用的是队列. 但是这个的子树的结点是先进后出的,所以我们使用栈更加方便. 而且为了方便,我用了两个栈,因为不是每一次都是先进左子树再进右子树的. 代码: 1 /* 2 struct TreeNode { 3 int val; 4 struct TreeNode *left; 5 struct TreeNod

剑指offer61 按之字形顺序打印二叉树

另一种自己写的解法 class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int> > result; vector<int> res; if(pRoot == NULL) return result; stack<TreeNode* > sta1; stack<TreeNode* > sta2; int n

按之字形顺序打印二叉树-剑指Offer

按之字形顺序打印二叉树 题目描述 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推. 思路 根据题意,每行的节点的访问顺序是相反的,我们可以用两个栈来隔行存储,一个栈中根据“左结点->右结点”的顺序访问另一个栈的栈顶元素,而另一个栈根据“右子树->左子树”的顺序访问另一个栈的栈顶元素,直到两个栈都为空 代码 import java.util.ArrayList; import java.util.St

《剑指offer》:[61]按之字形顺序打印二叉树

题目:请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三层再按照从左到右打印,其他行以此类推. 例如:按之字形顺序打印二叉树的结果如下图: 打印结果: 1 3,2 4,5,6,7 15,14,13,12,11,10,9,8 方案:利用两个栈.时间复杂度O(N)+辅助空间2*O(N). 具体方法:我们在打印某一结点时,把下一层的子结点保存到相应的栈里.如果当前打印的是奇数层(例如第一层,第三层...第2*n+1层),则先保存左子结点再保存右子

按之字形顺序打印二叉树(剑指offer+队栈的应用)

按之字形顺序打印二叉树 参与人数:703时间限制:1秒空间限制:32768K 通过比例:25.31% 最佳记录:0 ms|8552K(  ) 题目描述 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推. 题意:看测试用例 测试用例: {8,6,10,5,7,9,11} 对应输出应该为: [[8],[10,6],[5,7,9,11]] 思路:用一个布尔量控制从左到右还是从右到左的顺序:先放入栈中,然后把他

剑指OFFER之调整数组顺序使奇数位于偶数前面找(九度OJ1516)

题目描述: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变. 输入: 每个输入文件包含一组测试案例.对于每个测试案例,第一行输入一个n,代表该数组中数字的个数.接下来的一行输入n个整数.代表数组中的n个数. 输出: 对应每个测试案例,输入一行n个数字,代表调整后的数组.注意,数字和数字之间用一个空格隔开,最后一个数字后面没有空格. 样例输入: 5 1 2 3 4 5 样例输

【剑指offer】调整数组顺序

转载请注明出处:http://blog.csdn.net/ns_code/article/details/25829395 剑指offer上的第14题,九度OJ为了确保输出的结果的唯一性,在输出上做了修改,因此采用的方法自然与书本上不同,这里没有限制,思来想去还是用最简单的方法来做了,非常简单的方法,直接上代码. 题目描述: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变.

按之字形顺序打印二叉树

题目描述 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vect