返回

[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 得到想要的输出,代码如下:

#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

Built with Hugo
Theme Stack designed by Jimmy