使用 oh-my-zsh

题目描述

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

思路分析

• 基础——理解二叉树层序遍历，理解栈的特点
• 方法——辅助变量巧用：状态确认。用一个值确认当前的层的奇偶，打印节点。一个值确认下一层的奇偶，存储新节点。
• 思路巧妙之处：双栈的应用，辅助变量，在打印节点的同时，按照奇偶层存储下一层的节点

/*
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<vector<int> > res;
        // 非法判断
        if (pRoot == nullptr) {
            return res;
        }
        // 辅助变量
        stack<TreeNode*> s[2];// 两个栈存储奇偶层的节点
        int current = 0;// 标志当前的层的奇偶
        int next = 1;// 标志下一层的奇偶
        vector<int> level;
        
        // 遍历循环，算法主体
        s[current].push(pRoot);// 存储第一层的根节点
        while (!s[0].empty() || !s[1].empty()) {
            // 读取数据
            TreeNode* p = s[current].top();
            s[current].pop();
            
            //存储结果数据
            level.push_back(p->val);
            
            // 节点压栈
            if (current == 0) {// 当前偶数层，下一层子节点从左到右压栈
                if (p->left != nullptr) {
                    s[next].push(p->left);
                }
                if (p->right != nullptr) {
                    s[next].push(p->right);
                }
            } else { // 当前奇数层，下一层子节点从右到左压栈
                if (p->right != nullptr) {
                    s[next].push(p->right);
                }
                if (p->left != nullptr) {
                    s[next].push(p->left);
                }
            }
            
            // 辅助变量变换
            if (s[current].empty()) { // 当前层没有待打印的节点
                // 奇偶层变换
                current = 1 - current;
                next = 1 - next;
                res.push_back(level);// 存储当前层的节点输出顺序数据，到返回结果中
                level.clear();// 清楚存储的当前层节点数据
            }
            
        }

        // 返回结果
        return res;
    }
    
};

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com