题解 | #按之字形顺序打印二叉树#

按之字形顺序打印二叉树

http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

解法一:使用队列

据题意,需要按照每一层的方式打印二叉树,因此较为直接的解法为「层次遍历」。

二叉树的层次遍历通过队列实现较为方便,步骤如下:

  1. 初始情况,根结点入队列;
  2. 定义变量size记录当前队列长度;
  3. 对于「当前队列」,遍历其所有元素:依次出队列、访问该元素、左右孩子入队列。注意:新入队列的「左右孩子」应当在下一层被访问,因此循环次数为size次。
  4. 重复上述步骤直至队列为空。

步骤如图所示。

图片说明

此外,此题目要求「之字形」打印,因此定义变量level记录当前层的打印方向。

代码如下:

/*
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)
            return res; 
        queue<TreeNode*> q; // 定义队列
        q.push(pRoot); // 根结点入队列
        int level = 0;
        while (!q.empty()) {
            vector<int> arr; // 定义数组存储每一行结果
            int size = q.size(); // 当前队列长度
            for (int i = 0; i < size; i++) {
                TreeNode* tmp = q.front(); // 队头元素
                q.pop(); 
                if (!tmp) // 空元素跳过
                    continue;
                q.push(tmp->left); // 左孩子入队列
                q.push(tmp->right); // 右孩子入队列
                if (level % 2 == 0) {
                    // 从左至右打印
                    arr.push_back(tmp->val);
                } else { // 从右至左打印
                    arr.insert(arr.begin(), tmp->val);
                }
            }
            level++; // 下一层,改变打印方向
            if (!arr.empty())
                res.push_back(arr); // 放入最终结果
        }
        return res;
    }

};

该方法遍历到树的所有结点,时间复杂度为O(N);该方法定义了队列q,空间复杂度为O(N)。

解法二:使用栈

由本题所要求的「之字形打印」,可以联想到栈的「先入后出」的特性。由于栈仅能在一端进行入栈出栈操作,因此需要定义两个栈,交替使用。

步骤如下(如图所示):

  1. 定义两个栈stk1,stk2;将根结点入栈stk1;
  2. 对于下一层,应是「从右至左」打印,因此需要遍历栈stk1、访问每一个元素,并将每一元素的孩子按照「先右孩子、后左孩子」的顺序入栈stk2;将访问的结点保存;
  3. 对于下一层,应是「从左至右」打印,因此需要遍历栈stk2、访问每一个元素,并将每一元素的孩子按照「先左孩子、后右孩子」的顺序入栈stk1;将访问的结点保存;
  4. 重复上述操作,直至两个栈全为空。

图片说明

根据上述思路,实现的代码如下:

/*
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) 
            return res; 
        stack<TreeNode*> stk1, stk2; // 定义两个栈
        stk1.push(pRoot); // 根结点入栈
        while (!stk1.empty() || !stk2.empty()) { // 两个栈全空时循环结束
            vector <int> arr; 
            while (!stk1.empty()) {
                TreeNode* p = stk1.top(); 
                stk1.pop(); 
                arr.push_back(p->val); // 访问栈顶
                if (p->left) stk2.push(p->left); // 左孩子入栈
                if (p->right) stk2.push(p->right); // 右孩子入栈
            }
            if (arr.size())
                res.push_back(arr); // 保存结果
            arr.clear(); // 清空
            while (!stk2.empty()) {
                TreeNode* p = stk2.top(); 
                stk2.pop(); 
                arr.push_back(p->val); // 访问栈顶
                if (p->right) stk1.push(p->right); // 右孩子入栈
                if (p->left) stk1.push(p->left); // 左孩子入栈
            }
            if (arr.size())
                res.push_back(arr); // 保存结果
        }
        return res;
    }

};

该方法遍历到树的所有结点,时间复杂度为O(N);该方法定义了双栈,空间复杂度为O(N)。

全部评论
2和3步写错了啊,2是先左后右,3是先右后左
点赞 回复 分享
发布于 2023-09-08 11:06 广东

相关推荐

头像
11-21 11:39
四川大学 Java
是红鸢啊:忘了还没结束,还有字节的5k 违约金
点赞 评论 收藏
分享
29 3 评论
分享
牛客网
牛客企业服务