0%

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

题目描述

题目链接: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