leetcode 145后序遍历的递归迭代遍历

1. 题目：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/ 2. 思路一：递归遍历 后序遍历的规则：左右中 ，先遍历左子树，再遍历右子树，最后遍历中间节点。 通过递归方式，一层一层直到遍历到树最左端的节点 ，将节点入数组，返回到上一 层节点，在遍历右节点。一直这样递归下去

写法一：

class Solution { public: vector<int>vec; vector<int> postorderTraversal(TreeNode* root) { if(root==NULL) return vec; postorderTraversal(root->left); postorderTraversal(root->right); vec.push_back(root->val); return vec; } };

写法二：

class Solution { public: vector<int>vec; vector<int> postorderTraversal(TreeNode* root) { if(root) { postorderTraversal(root->left); postorderTraversal(root->right); vec.push_back(root->val); } return vec; } };

3.思路二：迭代遍历

后序遍历规则是左右中，而前序遍历的规则是根左右，如果对一棵树进行根右左的遍历再对得到的数组进行反转就可得到左右根的结果。 根右左的遍历：1、先将头节点入栈，在栈不为空的情况下循环 2、 将栈顶元素弹出，赋给一个指针节点，不为空就就将 结点的数入数组，为空就进行下一次循环 3、将左子树入栈，将右子树入栈。

```cpp class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int>vec; stack<TreeNode*>stk; stk.push(root); while(!stk.empty()){ TreeNode*node=stk.top(); stk.pop(); if(node!=NULL) vec.push_back(node->val); else continue; stk.push(node->left); stk.push(node->right); } reverse(vec.begin(),vec.end()); return vec; } };