144. 二叉树的前序遍历
题目链接：
https://leetcode.cn/problems/binary-tree-preorder-traversal/
算法思想：
根据前序遍历的定义：中左右
先把读取当前节点值，再递归遍历左子树，右子树
注意递归返回的条件：遍历到当前节点为空的时候返回。
用vec存储返回值了，因此return没有值
代码：
递归法实现：
class Solution {
public:
void preorder(TreeNode* root, vector<int>& vec)
{
if(root==NULL)
return ;
vec.push_back(root->val);
preorder(root->left, vec);
preorder(root->right, vec);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vec;
preorder(root, vec);
return vec;
}
};
迭代法实现：
算法思想：用栈来模拟递归的过程。
注意：因为前序遍历是先遍历左子节点，再遍历右子节点，因此栈放入的顺序是先放入右节点，再放入左节点。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
vector<int> res;
st.push(root);
while(!st.empty())
{
TreeNode* cur = st.top();
st.pop();
if(cur!=NULL)
{
res.push_back(cur->val);
}
else
continue;
st.push(cur->right);
st.push(cur->left);
}
return res;
}
};
145. 二叉树的后序遍历
题目链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/
算法思想： 左右中遍历。
代码：
后序遍历：
递归法：
class Solution {
public:
void postorder(TreeNode* cur, vector<int>& res)
{
if(cur==NULL)
{
return ;
}
postorder(cur->left, res);
postorder(cur->right, res);
res.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorder(root, res);
return res;
}
};
迭代法：
借鉴于前序遍历：中左右
转化下，实现成为中右左
反转下，变成左右中，即为后续遍历的结果
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
st.push(root);
vector<int> res;
while(!st.empty())
{
TreeNode* cur = st.top();
st.pop();
if(cur!=NULL)
{
res.push_back(cur->val);
}
else
continue;
st.push(cur->left);
st.push(cur->right);
}
reverse(res.begin(), res.end());
return res;
}
};
94. 二叉树的中序遍历
题目链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/
算法思想：中序遍历就是把当前节点的遍历放在中间。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void inorder(TreeNode*root, vector<int> & vec)
{
if(root==NULL)
return;
inorder(root->left, vec);
vec.push_back(root->val);
inorder(root->right, vec);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> vec;
inorder(root, vec);
return vec;
}
};
迭代法：
算法思想：
由于中序遍历当前访问的节点和要读取的节点不是同一个，因此需要借助于指针操作。
指针指向遍历的元素，栈顶存储要处理的元素。
指针遍历的元素不一定会处理，不处理的话就放入栈中存储起来，当指针为空时，说明可以开始处理栈的元素里，此时弹出栈顶，相当于处理中间节点，指针接着遍历右子树。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
//用一个指针来记录要处理的节点
TreeNode* cur = root;
stack<TreeNode*> st;
vector<int> res;
while(cur!=NULL || !st.empty())
{
if(cur != NULL) //表示要处理的节点和当前节点不一致,cur表示当前访问的
{
st.push(cur);
cur = cur->left; //处理左节点
}
else
{
TreeNode* node = st.top();
st.pop();
res.push_back(node->val); //处理中节点
cur = node;
cur = cur->right; //处理右节点
}
}
return res;
}
};
