迭代遍历关键在于记忆
1.采用迭代, 也就是非递归的形式进行前序/中序/后序遍历
2.对于前序和中序, 都是采用的是迭代的形式进行遍历, 因为树节点没有返回的指针, 所以不能回去访问, 也就是不能直接游走遍历, 所以需要用栈记下来 [上一次访问的根节点是哪个], 然后从栈里面取出来, 这样就能继续迭代遍历了
144.二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：输入：root = [1,null,2,3] 输出：[1,2,3]
示例 2：输入：root = [] 输出：[]
示例 3：输入：root = [1] 输出：[1]
示例 4：输入：root = [1,2] 输出：[1,2]
示例 5：输入：root = [1,null,2] 输出：[1,2]
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr) {
return ans;
}
stack<TreeNode*> preNode;
while (root != nullptr || !preNode.empty()) {
// 持续下钻走到最左下角的叶子节点
while (root != nullptr) {
ans.push_back(root->val);
preNode.push(root);
root = root->left;
}
// 回退到上一个根节点, 我们已经通过栈顶元素保存了上一个根节点
root = preNode.top();
preNode.pop();
// 然后再去访问这个根节点的右边孩子节点
root = root->right;
}
return ans;
}
};
94.二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：输入：root = [] 输出：[]
示例 3：输入：root = [1] 输出：[1]
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr) {
return ans;
}
stack<TreeNode*> preNode;
while (root != nullptr || !preNode.empty()) {
// 持续下钻走到最左下角的叶子节点
while (root != nullptr) {
preNode.push(root);
root = root->left;
}
// 回退到上一个根节点, 我们已经通过栈顶元素保存了上一个根节点
root = preNode.top();
preNode.pop();
ans.push_back(root->val);
// 然后再去访问这个根节点的右边孩子节点
root = root->right;
}
return ans;
}
};
二叉树的后序遍历和 [前序/中序] 有所不同,
1.迭代地按照先 [根] 然后 [左右孩子] 进行遍历得到一个根左右的结果, 然后我们将结果直接翻转, 得到 [左右孩子] 和 [根] 的结果
145.二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：输入：root = [1,null,2,3] 输出：[3,2,1]
示例 2：输入：root = [] 输出：[]
示例 3：输入：root = [1] 输出：[1]
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
if (root == nullptr) {
return ans;
}
stack<TreeNode*> preNode;
preNode.push(root);
while (!preNode.empty()) {
root = preNode.top();
preNode.pop();
ans.push_back(root->val);
if (root->left != nullptr) {
preNode.push(root->left);
}
if (root->right!= nullptr) {
preNode.push(root->right);
}
}
// 反转遍历的结果: [根][左右] => [左右][根]
reverse(ans.begin(), ans.end());
return ans;
}
};
转载请注明来源, from goldandrabbit.github.io
