# LeetCode Hard 145. Binary Tree Postorder Traversal

tags: leetcode

風邪は治ったけど，花粉症がキツイ．

次の総理大臣は花粉症を撲滅してほしい．

問題

• Explore
• Problems

アイデア

木を探索する際の順序として以下の図ように

• Inorder(左→根→右)
• Preorder(根→左→右)
• Postorder(左→右→根)

があります

ノードが5つの木の場合を図示すると以下の通りです

解法1(recursive)

InorderとPreorderと同じ要領でやるだけです．

Postorderは左，右，根の順番に答えの配列に格納します．

計算量

ノードの数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • 再帰の深さを考えても答えの配列の方が大きいので$O(N)$

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) {
    if (!root)
      return {};
      
    vector<int> res;      
    helper(root, res);
    return res;
  }
private:
  void helper(TreeNode* node, vector<int>& res) {
    if (!node)
      return;
    
    if (node->left)
      helper(node->left, res);
    if (node->right)
      helper(node->right, res);
    res.push_back(node->val);
  }
};

解法2(iterative)

再帰だと簡単に書けるけど反復的に書くのは面倒ですね...

Post-Orderの場合はスタックを2つ使うと上手く行きます．

注意するのはスタックはLIFO(Last-in First-out)なので，最後に入れたものが最初に出ます．

下のコードでは最初のwhileで，左，右の順番にスタックにノードを入れているので，右，左の順番に出ます．その結果根→右→左にrevResにノードが入っており，これを取り出すと求める順番となっています．

計算量

• 時間計算量
  • $O(N)$
• 空間計算量
  • 新たなスタックに必要な空間計算量が$O(N)$です
  • よって，$O(N)$
  • もし，答えを配列で格納する必要がない場合は$O(\log N)$で抑えられますが，余分に必要です

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) {
    if (!root)
      return {};
    
      stack<TreeNode*> nodeStack;
    stack<int> revRes;
    vector<int> res;
    nodeStack.push(root);
    while (!nodeStack.empty()) {
      auto curNode = nodeStack.top();
      nodeStack.pop();
      revRes.push(curNode->val);
      if (curNode->left)
        nodeStack.push(curNode->left);
      if (curNode->right)
        nodeStack.push(curNode->right);
    }
    while (!revRes.empty()) {
      res.push_back(revRes.top());
      revRes.pop();
    }
    return res;
    }
};