LeetCode 145二叉树的后序遍历
程序员文章站
2022-05-20 13:49:43
...
LeetCode 145二叉树的后序遍历
- 题目简述:给定一个二叉树,返回它的 后序 遍历。
- 输入:[1,null,2,3] 输出:[3,2,1]
- 思路:递归
class Solution {
public:
vector<int> res;
void dfs(TreeNode *root)
{
if(!root) return;
dfs(root->left);
dfs(root->right);
res.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
};
- 思路:栈模拟递归
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while(root || stk.size())
{
while(root)
{
stk.push(root);
root = root->left;
}
auto cur = stk.top();
root = cur->right;
//如果当前栈顶元素的右节点不空就while循环加入栈中,为空就处理当前节点
if(!root)
{
res.push_back(cur->val);
stk.pop();
//如果弹出的栈顶元素是新栈顶元素的右节点,就处理新栈顶元素
//即处理完右节点后处理根节点
while(stk.size() && cur == stk.top()->right)
{
cur = stk.top();
res.push_back(cur->val);
stk.pop();
}
}
}
return res;
}
};
- 迭代:先序遍历的反转,但是要由于栈先进后出,因此先压左节点后压右节点,后序遍历是
左右根
,反转前是根右左
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if(!root) return res;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty())
{
root = stk.top();
stk.pop();
res.push_back(root->val);
if(root->left) stk.push(root->left);
if(root->right) stk.push(root->right);
}
reverse(res.begin(), res.end());
return res;
}
};