题解 | #按之字形顺序打印二叉树#
按之字形顺序打印二叉树
http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0
解法一:使用队列
据题意,需要按照每一层的方式打印二叉树,因此较为直接的解法为「层次遍历」。
二叉树的层次遍历通过队列实现较为方便,步骤如下:
- 初始情况,根结点入队列;
- 定义变量size记录当前队列长度;
- 对于「当前队列」,遍历其所有元素:依次出队列、访问该元素、左右孩子入队列。注意:新入队列的「左右孩子」应当在下一层被访问,因此循环次数为size次。
- 重复上述步骤直至队列为空。
步骤如图所示。
此外,此题目要求「之字形」打印,因此定义变量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)。
解法二:使用栈
由本题所要求的「之字形打印」,可以联想到栈的「先入后出」的特性。由于栈仅能在一端进行入栈出栈操作,因此需要定义两个栈,交替使用。
步骤如下(如图所示):
- 定义两个栈stk1,stk2;将根结点入栈stk1;
- 对于下一层,应是「从右至左」打印,因此需要遍历栈stk1、访问每一个元素,并将每一元素的孩子按照「先右孩子、后左孩子」的顺序入栈stk2;将访问的结点保存;
- 对于下一层,应是「从左至右」打印,因此需要遍历栈stk2、访问每一个元素,并将每一元素的孩子按照「先左孩子、后右孩子」的顺序入栈stk1;将访问的结点保存;
- 重复上述操作,直至两个栈全为空。
根据上述思路,实现的代码如下:
/* 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)。