题目描述
给你二叉树的根节点 root ,返回它节点值的 前序 / 中序 / 后序 遍历。
递归写法
LeetCode_0144. 前序
中左右
void myPreorder(TreeNode* root, vector<int>& ans) {
if(!root) {
return;
}
ans.emplace_back(root->val);
myPreorder(root->left, ans);
myPreorder(root->right, ans);
return;
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
myPreorder(root, ans);
return ans;
}
LeetCode_0094. 中序
左中右
void myInorder(TreeNode* root, vector<int>& ans) {
if(!root) {
return;
}
myInorder(root->left, ans);
ans.emplace_back(root->val);
myInorder(root->right, ans);
return;
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
myInorder(root, ans);
return ans;
}
LeetCode_0145. 后序
左右中
void myPostorder(TreeNode* root, vector<int>& ans) {
if(!root) {
return;
}
myPostorder(root->left, ans);
myPostorder(root->right, ans);
ans.emplace_back(root->val);
return;
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
myPostorder(root, ans);
return ans;
}
迭代写法
栈内是待访问的结点,current是当前搜索到的结点。
LeetCode_0144. 前序
从root开始,先访问current,right入栈,转向left搜索。
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> myStack;
// 搜索从root开始
TreeNode *current = root;
// 当前搜索到叶子且没有待搜索结点时,结束搜索
while(current || !myStack.empty()) {
// 当前结点
if(current) {
// 中
ans.emplace_back(current->val);
// 右孩子待搜索
myStack.emplace(current->right);
// 搜索左孩子
current = current->left;
// 当前结点走到头了,就取出一个待搜索结点
} else {
current = myStack.top();
myStack.pop();
}
}
return ans;
}
LeetCode_0094. 中序
从root开始,current先入栈,转向left。
每当current搜索到头了,回退一步访问栈顶元素,转向栈顶元素的right。(一路向左,回退访问,向右)
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> myStack;
TreeNode* current = root;
while(current || !myStack.empty()) {
if(current) {
myStack.emplace(current);
current = current->left;
} else {
current = myStack.top();
myStack.pop();
ans.emplace_back(current->val);
current = current->right;
}
}
return ans;
}
LeetCode_0145. 后序
解法跟前序非常相似。
后续遍历是左右中,反过来 就是 中右左,跟前序一样,也是先访问自己再访问孩子。
因此只需要解出 中右左 ,再reverse()就可以了。
从root开始搜索,left先入栈,转向搜索right。
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> myStack;
TreeNode *current = root;
while(current || !myStack.empty()) {
if(current) {
ans.emplace_back(current->val);
myStack.emplace(current->left);
current = current->right;
} else {
current = myStack.top();
myStack.pop();
}
}
reverse(ans.begin(), ans.end());
return ans;
}
标签:遍历,return,current,vector,二叉树,ans,myStack,root,LeetCode
From: https://www.cnblogs.com/GaogaoBlog/p/18415447