迭代思路:
可以这么理解,迭代是用自己实现的栈去模拟系统栈的功能,进一次循环则是遍历一次根节点,遍历节点非空或者是栈中还有等待遍历的节点时候,循环需要一直做。
前序遍历(顺序:根 -> 左 -> 右):
1. 遍历当前子树,由于先遍历根,需要记录下答案(res.push_back(root));
2. 遍历左子树前,因为遍历完之后需要回溯,则当前根的信息需要保存到栈中,则stk.push(root);
3. 同理遍历右子树
中序遍历(顺序:左 -> 根 -> 右):
1. 遍历左子树前,因为遍历完之后需要回溯,则当前根的信息需要保存到栈中,则 stk.push(root);
2. 遍历完左子树后,root = stk.top() 表示回到根节点,res.push_back(root=>val);
3. 同理遍历右子树
后序遍历(顺序:左 -> 右 -> 根):
方法一:
直接把根 -> 右 -> 左遍历的结果reverse一遍
方法二:
由于是最后遍历根节点,则需要知道回溯到栈顶时,是从左子树回溯回来还是右子树,那么记录一个last变量
1. 遍历左子树前,因为遍历完之后需要回溯,则当前根的信息需要保存到栈中,则 stk.push(root);
2. 遍历完左子树后,回到根节点,判断last是否是root->right如果是或者右子树不存在则表示已经遍历完右子树,弹栈,否则,root = root->right;
前序遍历
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root || stk.size()) {
while (root) {
res.push_back(root->val);
stk.push(root);
root = root->left;
}
root = stk.top()->right;
stk.pop();
}
return res;
}
中序遍历
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root || stk.size()) {
while (root) {
stk.push(root);
root = root->left;
}
res.push_back(stk.top()->val);
root = stk.top()->right;
stk.pop();
}
return res;
}
后序遍历
后序遍历的顺序为:左、右、根,先遍历出来根、右、左,然后镜像,就得到后续遍历了
// 方法一:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root || stk.size()) {
while (root) {
res.push_back(root->val);
stk.push(root);
root = root->right;
}
root = stk.top()->left;
stk.pop();
}
reverse(res.begin(), res.end());
return res;
}
// 方法二:
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> res;
TreeNode* last = nullptr;
while (root || stk.size()) {
while (root) {
stk.push(root);
root = root->left;
}
root = stk.top();
if (!root->right || root->right == last) {
res.push_back(root->val);
stk.pop();
last = root;
root = nullptr;
} else root = root->right;
}
return res;
}
};