LeetCode刷题（118）～二叉树的后序遍历【递归｜ 迭代】

题目描述

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3] 1 \ 2 / 3 

输出: [3,2,1]

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解答 By 海轰

vector<int> ans; vector<int> postorderTraversal(TreeNode* root) { if(root!=nullptr) { postorderTraversal(root->left); postorderTraversal(root->right); ans.push_back(root->val); } return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

运行结果

提交代码（迭代）

vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> call; if(root!=nullptr) call.push(root); while(!call.empty()){ TreeNode *t = call.top(); call.pop(); if(t!=nullptr){ call.push(t);  //在右节点之前重新插入该节点，以便在最后处理（访问值） call.push(nullptr); //nullptr跟随t插入，标识已经访问过，还没有被处理 if(t->right) call.push(t->right); if(t->left) call.push(t->left); }else{ res.push_back(call.top()->val); call.pop(); } } return res; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108349387