题目描述

题目链接：145. Binary Tree Postorder Traversal

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]

Follow Up

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

解题思路

方法一：递归

利用递归可以很简单通过 dfs 得到想要的输出，代码如下：

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

#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

其他题目：
GitHub: Leetcode-C++-Solution
博客： Leetcode-Solutions