问题一：二叉树的前序遍历
解题思路
-
递归法有手就行，本次来试一下迭代法。
-
迭代法都需要用到栈结构。利用栈先入后出的特点依次将元素遍历。
代码如下
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> st;
st.push(root);//一定记得先把这个根节点压入栈
while(!st.empty())
{
//先把栈内元素存储在一个临时变量temp里，再把它出栈
TreeNode* temp = st.top();
st.pop();
//接下来操作temp就可以得到对应的节点值
res.push_back(temp->val);
//先右后左，因为栈先入后出
if(temp->right)
{
st.push(temp->right);
}
if(temp->left)
{
st.push(temp->left);
}
}
return res;//出来就是中左右，前序遍历完成
}
};
问题二：二叉树的后序遍历
解题思路
代码如下
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> st;
st.push(root);//一定记得先把这个根节点压入栈
while(!st.empty())
{
//先把栈内元素存储在一个变量里，再把它出栈
TreeNode* temp = st.top();
st.pop();
res.push_back(temp->val);
if(temp->left)
{
st.push(temp->left);
}
if(temp->right)
{
st.push(temp->right);
}
}
//出栈后是中右左。想要是后序遍历(左右中)直接reverse即可。
reverse(res.begin(), res.end());//注意reverse格式
return res;
}
};
问题三：二叉树的中序遍历
解题思路
- 为什么中序遍历不同呢？因为前序后序都是操作根节点，遍历根节点；而中序遍历是操作根节点，遍历最左子树。如何才能遇到根节点的时不动它呢？答案是先push不pop。详见代码。
代码如下
解法1
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root != nullptr || !stk.empty()) {
while (root != nullptr) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
};
问题四：二叉树的层序遍历
解题思路
- 下述思路来自算法集结号。新建一个node结构体用于存放一个节点和当前所在层数。
代码如下
struct node{
TreeNode *p;
int depth;
};
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
int last = 0;
vector<int> current;
queue<node> que; //队列类型为node，存放当前层节点，及时传给current
que.push((node){root, 0});
while(!que.empty())
{
node temp = que.front();
que.pop();
if(temp.depth != last) //如果不在同一层，赶快把current拿出来
{
res.push_back(current);
current.clear();
last = temp.depth;
}
current.push_back(temp.p->val);
if(temp.p->left)
{
que.push((node){temp.p->left, temp.depth + 1});
}
if(temp.p->right)
{
que.push((node){temp.p->right, temp.depth + 1});
}
}
res.push_back(current);
return res;
}
};
解法2
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector <vector <int>> ret;
if (!root) {
return ret;
}
queue <TreeNode*> q;
q.push(root);
while (!q.empty()) {
int currentLevelSize = q.size();
ret.push_back(vector <int> ());
for (int i = 1; i <= currentLevelSize; ++i) {
auto node = q.front(); q.pop();
ret.back().push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
}
return ret;
}
};
解法3——来自《代码随想录》卡尔的解法
vector<vector<int>> levelOrder(TreeNode* root)
{
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty())
{
int size = que.size();
vector<int> vec;
// 这里一定要使用固定大小的size,不要使用que.size(),因为que.size()是不断变化的
for (int i = 0; i < size; i++)
{
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
补齐LC中缺失的部分——建立二叉树与打印二叉树
代码如下：
TreeNode* build(vector<int>& nums) {
if (nums.empty() || nums[0] == -1) return nullptr;
// 将数字转换成 TreeNode
vector<TreeNode*> nodes;
for (int i = 0; i < nums.size(); i++) {
TreeNode* cur = nullptr;
if (nums[i] != -1) cur = new TreeNode(nums[i]);
nodes.push_back(cur);
}
// 父子结点关联，i 的左右孩子下标为 2 * i + 1 和 2 * i + 2
// 由于输入约定是一个满二叉树，所以只要保证最后一个右孩子不越界
for (int i = 0; 2 * i + 2 < nums.size(); i++) {
if (!nodes[i]) continue;
nodes[i]->left = nodes[2 * i + 1];
nodes[i]->right = nodes[2 * i + 2];
}
return nodes[0];
}
int main() {
// 输入序列格式：
// 1. 满二叉树
// 2. 按照层序遍历的顺序
// 3. 空结点用 -1 表示
vector<int> nums = {4,2,5,1,3,-1,6};
TreeNode* root = build(nums);
vector<int> ans = inorderTraversal(root);//这个地方调用了上述我们写的函数，前中后层序遍历我们替换掉即可。
for (auto val: ans) {
cout << val << " ";
}
return 0;
}
问题五：二叉树的锯齿形层序遍历
解题思路
-
所谓锯齿形层序遍历就是多了一个栈st用来存储奇数层节点，其他情况和层序遍历基本相同，只不过要认真一些。
-
奇数行放到栈中，偶数行放到vector中。最后一行需要单独处理，使用一个判断语句考虑奇偶，再push即可。
代码如下
struct node
{
TreeNode* p;
int depth;
};
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if(!root) return res;
vector<int> current; //存储当前行 (偶数)
stack<int> st; //也是存储当前行 (奇数行)
queue<node> que; //BFS快乐队列
que.push((node){root, 0}); //把起点放入队列
int last = 0; //上一个节点的层深
while(!que.empty())
{
node temp = que.front();
que.pop();
while(last != temp.depth) //判断是不是新的一层。
{
while(!st.empty())
{
current.push_back(st.top()); //如果是新的一层，就先判断栈(偶数)是否为空。如果非空，说明此时遍历奇数行，直接把栈中元素放入current
//如果st内无元素，那它就一定都在current里了。
st.pop();
}
//此时该行节点都已存储在current中了。
res.push_back(current);
current.clear();
last = temp.depth;
}
//至此，完成将上一行节点插入res动作。
if(temp.depth % 2 != 0)
{
st.push(temp.p->val); //奇数层放到栈中，再由上面的st.empty()判断语句放入current
}
else
{
current.push_back(temp.p->val); //偶数层直接放到current
}
//判断奇数层还是偶数层
//下述判断和层序遍历同理
if(temp.p->left)
{
que.push((node){temp.p->left, temp.depth + 1});
}
if(temp.p->right)
{
que.push((node){temp.p->right, temp.depth + 1});
}
}
//判断最后一层的奇偶性。先检测栈
while(!st.empty())
{
current.push_back(st.top());
st.pop();
}
res.push_back(current); //栈为空，就必定都在current里。
return res;
}
};
