## [Leetcode]145. Binary Tree Postorder Traversal(C++)

### 题目描述

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

### 例子

#### 例子 1

Input: root = [1,null,2,3] Output: [3,2,1]

#### 例子 2

Input: root = [] Output: []

#### 例子 3

Input: root = [1] Output: [1]

#### 例子 4

Input: root = [1,2] Output: [2,1]

#### 例子 5

Input: root = [1,null,2] Output: [2,1]

Recursive solution is trivial, could you do it iteratively?

### Constraints

• The number of the nodes in the tree is in the range `[0, 100]`.
• `-100 <= Node.val <= 100`

### 解题思路

#### 方法一：递归

``````#include <vector>
class Solution {
public:
std::vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> result;

dfs(root, result);

return result;
}

private:
void dfs(TreeNode* root, std::vector<int>& result) {
if (!root) return;
dfs(root->left, result);
dfs(root->right, result);
result.push_back(root->val);
}
};
``````
• 时间复杂度: O(n)
• 空间复杂度: O(h)

#### 方法二：迭代

GitHub 代码同步地址： 145.BinaryTreePostorderTraversal.cpp

Built with Hugo
Theme Stack designed by Jimmy