# 145. Binary Tree Postorder Traversal 二叉树的后序遍历

@TOC

## # 题目描述

Given a binary tree, return the postorder traversal of its nodes' values.

Example:

``````Input: [1,null,2,3]
1
\
2
/
3

Output: [3,2,1]
``````

Follow up: Recursive solution is trivial, could you do it iteratively?

## # 解题方法

### # 递归

C++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
vector<int> left = postorderTraversal(root->left);
vector<int> right = postorderTraversal(root->right);
res.insert(res.end(), left.begin(), left.end());
res.insert(res.end(), right.begin(), right.end());
res.push_back(root->val);
return res;
}
};
``````

Python代码如下：

``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
if not root: return res
if root.left:
res.extend(self.postorderTraversal(root.left))
if root.right:
res.extend(self.postorderTraversal(root.right))
res.append(root.val)
return res
``````

### # 迭代

C++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
TreeNode* node = st.top(); st.pop();
if (!node) continue;
res.push_back(node->val);
st.push(node->left);
st.push(node->right);
}
reverse(res.begin(), res.end());
return res;
}
};
``````

## # 日期

2019 年 9 月 20 日 —— 是选择中国互联网式加班？还是外企式养生？