Rust 版

はじめに

---

binary search tree の，先頭からk番目の数値を答える問題．

Rust で解いてみたので，慣れている C++で解いてみた．

コード全体

---

class Solution {
  tuple<TreeNode*, int> helper(TreeNode* root, int k) {
    if (!root) return { nullptr, k };
    TreeNode* node;
    int next;
    tie(node, next) = helper(root->left, k);
    if (!node) {
      if (next == 1) return { root, 0 };
      else return helper(root->right, next - 1);
    } else {
      return { node, 0 };
    }
  }
public:
  int kthSmallest(TreeNode* root, int k) {
    return get<0>(helper(root, k))->val;
  }
};

解説

---

事前準備

---

class Solution {
  tuple<TreeNode*, int> helper(TreeNode* root, int k) {

探索対象が空の場合はカウントしない

---

    if (!root) return { nullptr, k };

左再帰

---

探索対象の左にノードが存在する場合は，「それより小さい値」が存在するため，先にカウントする．

そして，k番目のノードが発見されたかをnodeに，残りカウントをnextに格納する．

    TreeNode* node;
    int next;
    tie(node, next) = helper(root->left, k);

分岐＆右再帰

---

左にk番目が合った場合はそれを返す．

無くて，自身がk番目であれば自身を返す．

どちらでもない場合はカウントを引き継ぎつつ右方向に再帰する．

    if (!node) {
      if (next == 1) return { root, 0 };
      else return helper(root->right, next - 1);
    } else {
      return { node, 0 };
    }
  }

ヘルパを実行

---

探索結果の値(val)を返す．

public:
  int kthSmallest(TreeNode* root, int k) {
    return get<0>(helper(root, k))->val;
  }
};

おわりに

---

ポインタの扱いが簡潔で良い点が心地よい．これによりメモリの危険性があることは，悩みどころだと感じる．

また，nullptrによるアーリーリターンが，複雑になりがちな再帰処理の中で，頭をすっきりさせることに多く寄与している印象がある．具体的に，「入力がからの場合はこの関数はすぐおしまい！」とすることで，頭の中で扱うことで，考慮すべき項目を一つ減らすことが出来ていた．

これに関しては，Rust のmatchに慣れると改善されるのだろうと思う．

参考

---

• https://en.cppreference.com/w/cpp/utilitytuple
• https://en.cppreference.com/w/cpp/utility/tupletie