一、前序
1.递归
略
2.非递归
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> res;
if(!root)
return res;
stack<TreeNode *> st;
st.push(root);
while(st.size())
{
TreeNode *temp = st.top();
st.pop();
res.push_back(temp->val);
if(temp->right)
st.push(temp->right);
if(temp->left)
st.push(temp->left);
}
return res;
}
二、中序
1.递归
略
2.非递归
啊啊啊学不会啊啊啊等学会了再来写吧。
三、后序
1.递归
略
2.非递归
// 巧妙的方法：前序遍历 根->左->右 变成 根->右->左 结果再reverse一下
vector<int> postorderTraversal(TreeNode *root)
{
vector<int> res;
if(!root)
return res;
stack<TreeNode *> st;
st.push(root);
while(st.size())
{
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(res.begin(),res.end());
return res;
}