Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Medium 144. Binary Tree Preorder Traversal

leetcode
tags: leetcode

非常に久しぶりです．

案の定，風邪を引いていました．皆さんも季節の変わり目には気を付けて下さい^_^(コロナじゃなくてよかったーーーーーー)

問題

アイデア

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

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

があります

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

解法1(recursive)

まずは根の値を答えの配列に入れ，次に左，右の部分木を見てそのノードの値を入れる再帰関数を書きます．

計算量

ノードの数を$N$として

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • 再帰関数の深さに応じて$O(\log 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> preorderTraversal(TreeNode* root) {
    if (!root)
      return {};
    
    vector<int> res;
    getNodeFromTree(root, res);
    return res;
  }
private:
  void getNodeFromTree(TreeNode* node, vector<int>& res) {
    if (!node)
      return;
    res.push_back(node->val);
    getNodeFromTree(node->left, res);
    getNodeFromTree(node->right, res);
  }
};

解法2(iterative)

上記の解答をwhileなどを使って反復的に書くだけです

std::stackを使うことで再帰関数を表現できます．

  • 最初に答えを格納する配列を作ります
  • 次にノードを入れるスタックを作ります
  • まずは根をスタックに入れます．
  • スタックが空になるまで以下の動作を繰り返します
    • スタックの先頭のノードの値を配列に入れて，スタックから削除する
    • そのノードの右のノードがあればスタックに入れる
    • そのノードの左のノードがあればスタックに入れる

計算量

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