TypeScriptでLeetCodeを始めました~Trees編~[後編] - ムスリムエンジニアbebetaroのブログ

先週はプライベートが忙しくブログ更新のタイミングが取れませんでした…😅
ここでずるずると更新できなくなるとまずいので、今回は意地で更新しています！あと今回は2問だけなので短いのも助かっています😤
飽き性なのでコンスタントに続けていくのは難しいですが、なんとかかんとかTop InterviewのEasy Collectionを終わらせるまでは続けていきたいですね。というわけで、今回はTreesの後編です！早速問題に移りましょう！

Binary Tree Level Order Traversal
Convert Sorted Array to Binary Search Tree
まとめ

Binary Tree Level Order Traversal

「あるバイナリツリーが与えられる。そのバイナリツリーのノードが持つ値を深さ毎に水平に分けたものを返せ」という問題です。
関数が返す値としては、バイナリツリーの形と同様の配列となります。以上を踏まえた自分の解法が以下になります！

const levelOrder = (root: TreeNode | null): number[][] => {
  if (root === null) {
    return [];
  }
  const ans: number[][] = [];
  traverseBTS(root, ans, 0);
  return ans;
};

const traverseBTS = (root: TreeNode | null, arr: number[][], depth: number) => {
  if (root === null) {
    return;
  } else {
    if (arr[depth] === undefined) {
      arr.push([]);
    }
    arr[depth].push(root.val);
  }
  traverseBTS(root.left, arr, depth + 1);
  traverseBTS(root.right, arr, depth + 1);
};

基本は深さ優先探索を行い、ひたすらTreeを潜っていきます。1層深く潜るとdepthをインクリメントしていく感じです。
その過程で引数として渡した配列に各ノードの値を挿入していきます。この時、配列がその深さの配列をまだ持っていない場合は新たにその階層の値を入れるための配列を挿入します。また、もしそのノードがnullであれば何もせず終わります。
これを左のノードを右より先に探索するように進めることで、最終的には答えの配列が完成します。また、JS/TSの配列は参照渡しであるため大元の関数から渡した配列がそのまま探索によりアップデートされますので、探索前に配列を作成し探索後はそれをそのまま返すだけでOKです！😄

Convert Sorted Array to Binary Search Tree

「ソート済の配列が渡される。そのソート済配列を用いてバイナリツリーを作成せよ」という問題です。バイナリツリーとはなんぞやということを考えると簡単ですね。バイナリツリーでは各ノードは2つの子要素を持ち、左の子要素が持つ値はそのノードよりも小さく、右の子要素が持つ値は大きいというルールに従って再帰的にTreeを作っていくと答えが導けます！以上に基づいた自分のコードが以下になります。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function sortedArrayToBST(nums: number[]): TreeNode | null {
  if (nums.length === 0) {
    return null;
  }
  if (nums.length === 1) {
    return new TreeNode(nums[0], null, null);
  }
  const mid = Math.floor(nums.length / 2);
  const left = sortedArrayToBST(nums.slice(0, mid));
  const right = sortedArrayToBST(nums.slice(mid + 1, nums.length));
  return new TreeNode(nums[mid], left, right);
}

まず配列に何もない場合は、TreeNodeを作れないのでnullを返します。
また、配列に1つの要素しかない場合、これも子要素を持たないので、2つの子要素をnull、valに唯一の値を割り当てたTreeNodeを作成して返します。そして、これは同時にTreeNodeの葉にもなりうります。
それ以上の長さの場合は、まずその深さにおける真ん中の値を求めます。それがこのノードの値となります。そして、その値を中心に左と右に分けて、再帰的にノードを構成していきます。これにより葉からノードが作られていき、最終的には根を返すため答えとなります！

まとめ

今回はTreesの後編ということで問題数も少なく、内容もEasyだったためちょっとあっさりした記事となりました😅
ただ、個人的には最近深さ優先探索を改めて勉強していたり、ちょうど今日のLeetCodeContestにもTreesが出たので、割とタイムリーなテーマに感じていたりもします。また、ブログをまとめる際に振り返って問題を見てみると簡単だなーっと感じるようになったり、解答当時(とはいえ、1ヶ月前程ですが…)のコードの稚拙さを感じたりとTrees周りは成長できているのではないかと自負しています。
同時に最近課題に感じているのはDPですね…。DPは使える幅が広いのでもっとマスターできるようになりたいです…。理論と同様に慣れも大事かと思いますので、引き続きDP関係の問題を解いていきたいと思います。また、最近は一部問題をRustで解いたりもするようになりました。Rustはまだまだ全然不慣れであれなのですが、Rustのコードでも解法を導いていけるようになるといいなっと思います！

そんな感じで今回でTreesは終わりです。次回はSorting and Searchingです。
こちらは2問だけでボリュームがないので1回に収まりそうですね！また、今回同様にあっさりした内容になりそうです…😅とはいえ、あっさりした方がブログとしては書きやすいので、ちゃんと週を空けずに書けるように頑張ります！💪