题目描述
算法1
队列 $O(n)$
按照层次遍历按层打印二叉树的方式,每层分开打印,然后对于每一层利用flag标记,第一层为false,之后每到一层取反一次,如果该层的flag为true,则记录的数组整个反转即可。
C++ 代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > Print(TreeNode* pRoot){
TreeNode* head = pRoot;
vector<vector<int>> res;
if(head == NULL)
return res;
queue<TreeNode*> temp;
temp.push(head);
TreeNode* p; //指向当前访问的节点。
bool flag = true; //表示当前行是否需要反转。
while(!temp.empty()){
vector<int> row;
int n = temp.size();
flag = !flag;
for(int i = 0; i < n; i++){
p = temp.front();
temp.pop();
row.push_back(p->val);
if (p -> left)
temp.push(p->left);
if (p -> right)
temp.push(p->right);
}
if (flag)
reverse(row.begin(),row.end());
res.push_back(row);
}
return res;
}
};
算法2
双栈法 $O(n)$
方法一用到了反转函数,反转我们能想到什么?肯定是先进后出的栈!
step 1:首先判断二叉树是否为空,空树没有打印结果。
step 2:建立两个辅助栈,每次依次访问第一个栈s1与第二个栈s2,根节点先进入s1.
step 3:依据依次访问的次序,s1必定记录的是奇数层,访问节点后,将它的子节点(如果有)依据先左后右的顺序加入s2,这样s2在访问的时候根据栈的先进后出原理就是右节点先访问,正好是偶数层需要的从右到左访问次序。偶数层则正好相反,要将子节点(如果有)依据先右后左的顺序加入s1,这样在s1访问的时候根据栈的先进后出原理就是左节点先访问,正好是奇数层需要的从左到右访问次序。
step 4:每次完一层访问,即一个栈为空,则将一维数组加入二维数组中,并清空以便下一层用来记录。
C++ 代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pRoot TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > Print(TreeNode* pRoot){
TreeNode* head = pRoot; //头结点
vector<vector<int>> res; //记录最终的结果
vector<int> row; //记录每一行的结果
//双栈
stack<TreeNode*> s1;
stack<TreeNode*> s2;
if(head == NULL)
//如果是空,则直接返回空vector
return res;
s1.push(head);
while(!s1.empty() || !s2.empty()){
// 访问奇数行,并将它的下一行(偶数行)加入栈中
while(!s1.empty()){
TreeNode* node = s1.top();
s1.pop();
row.push_back(node->val);
if (node -> left)
s2.push(node->left);
if (node -> right)
s2.push(node-> right);
}
// 将奇数行的结果row加入最终结果res中,并清空row的内容
if (row.size()) // !!
res.push_back(row);
row.clear();
// 访问偶数行,并将它的下一行(奇数行)加入栈中
while(!s2.empty()){
TreeNode* node = s2.top();
s2.pop();
row.push_back(node->val);
if(node->right)
s1.push(node->right);
if(node->left)
s1.push(node->left);
}
if (row.size()) // !!
res.push_back(row);
row.clear();
}
return res;
}
};
队列queue
的常用函数为:
push():将元素添加到队列的末尾。
pop():移除队列中的第一个元素。
front():返回队列中的第一个元素的引用。
back():返回队列中的最后一个元素的引用。
empty():检查队列是否为空,返回一个布尔值。
size():返回队列中元素的数量。
swap():交换两个队列的内容。
栈stack
的常用函数为:
push():将元素添加到栈的顶部。
pop():移除栈顶的元素。
top():返回栈顶的元素的引用。
empty():检查栈是否为空,返回一个布尔值。
size():返回栈中元素的数量。
vector
的常用函数为
push_back():将元素添加到向量的末尾。
pop_back():移除向量的最后一个元素。
size():返回向量中元素的数量。
empty():检查向量是否为空,返回一个布尔值。
clear():清空向量中的所有元素。
front():返回向量中的第一个元素的引用。
back():返回向量中的最后一个元素的引用。
at():返回指定索引处的元素的引用,带有边界检查。
operator[]:返回指定索引处的元素的引用,不带边界检查。
begin():返回指向向量第一个元素的迭代器。
end():返回指向向量末尾的下一个位置的迭代器。