TypeScriptでLeetCodeを始めました~Trees編~[前編]

今回からTrees編ということで、TypeScriptで書いていきます!
ちなみにTypeScriptはTrees以前からも選択できたのかもですが、自分が気付いていませんでした…😨
でもTypeScriptで書くとやはりnullチェックがしっかり入ったり、変な返り値も型で防止してくれるので事故が少ないですね!あとは引数にnullがunion型で指定されていると、「あ!これはnullが入りうるからその処理かかなきゃ!」と気づくこともできます!さらに、自分はVSCodeで書いているのですが、型による補完もめちゃくちゃありがたいです。JSはJSDoc形式で引数と返り値を書く必要があって少々面倒なんですよね…😅
これだけのメリットがあるため、今後の問題ではTypeScriptを選べる場合はTypeScriptで解答していきたいと思います。それでは、早速問題に移りましょう!

Maximum Depth of Binary Tree

「バイナリツリーが与えられる時、その深さの最大値を求めよ」という問題です。
まずバイナリツリーってなんぞやという話ですが、これは上記の問題の例を見ていただくのが一番分かりやすいと思います。頭にあるような根っことなるNodeから最大2つの子を持ちうり、どんどん下に降りていくというデータ構造です。この問題では、それを末端まで降りていった時、深さはどれくらいになっているかを求める必要があります。
それを踏まえて自分の答えは以下のようになりました!

// 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 maxDepth(root: TreeNode | null): number {
  if (root === null) {
    return 0;
  }
  const findDepthNumber = (depth: number, node: TreeNode): number => {
    if (node.left === null && node.right === null) {
      return depth;
    }
    const left = node.left ? findDepthNumber(depth + 1, node.left) : depth;
    const right = node.right ? findDepthNumber(depth + 1, node.right) : depth;

    return Math.max(left, right);
  };
  return findDepthNumber(1, root);
}

まず初期値となるrootがnullの場合は、それはもう深さがないので0を返します。rootがNodeとして与えられた時には、findDepthNumber関数にrootの深さ1とrootNodeを渡します。このfindDepthNumber関数は再帰関数でして、子Nodeを持たない、すなわち自身が末端である時はそれまでの深さを返します。また、自身が末端ではない時には、左と右の深さを求めます。この時、左と右のNodeが存在しなければ、それまでの深さを使います。また、Nodeがある時にはそのNodeを用いてさらにfindDepthNumber関数を走らせます。これにより最終的には左右それぞれの末端までの深さが求まりますので、そのより深い方を返り値として返すことで答えになります。Treesは一見すると取っ付きにくさを感じますが、このように取り組んでみると意外と解けちゃう問題が多いです!

Validate Binary Search Tree

続いての問題は、「与えられたバイナリツリーが適切なものか判定せよ」という問題です。
これは、正直上手く解けなかったです。左の子Nodeは常に親Nodeより小さく、右の子Nodeは常に親より大きくなければならないという条件なのですが、自分は左に分岐した後の右のNodeや逆に右に分岐した後の左のNodeについてのロジックを上手く組み立てることができず、最終的にはSolutionに頼りました。それが以下の解答になります。

/**
 * 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 isValidBST(root: TreeNode | null): boolean {
  if (root === null) {
    return true;
  }
  return traverseBST(null, null, root);
}

const traverseBST = (
  high: number | null,
  low: number | null,
  root: TreeNode | null
): boolean => {
  if (root === null) {
    return true;
  }
  if (high !== null && root.val >= high) {
    return false;
  }
  if (low !== null && low >= root.val) {
    return false;
  }

  const left = traverseBST(root.val, low, root.left);
  const right = traverseBST(high, root.val, root.right);

  return left && right;
};

isValidBST関数の中で、traverseBST関数を呼び出します。このtraverseBSTは引数としてhigh, low, rootを受け取り、もしもrootがnullの場合はtrueを返しますが、rootがhighより大きい場合やlowより小さい場合はバイナリツリーとして適切ではないとしてfalseを返します。このhighとlowを決めるロジックなのですが、その後に定義されているように左の子Nodeの場合はlowはそのまま(左に行くので現在の値よりどれだけ小さいかは気にしない)、highに現在の値を入れます。(左に行くので、現在の値よりも大きくなってはいけない)右のNodeには逆にhighはそのままでlowに現在の値が入ります。これらを再帰的に回し、途中に条件に反するものがあればfalseが返ってきますし、もし末端まで無事にたどり着けばバイナリツリーとして適正であるとしてtrueが返ってきます。また、左と右に分岐するたびにlowhighがアップデートしていくため、Treeが深く複雑になっていったとしても対応可能です。 この左と右の結果を最後にAND条件で判定したものをtraverseBSTの最終判定結果として返すことで答えとなります!

Symmetric Tree

「与えられたバイナリツリーがシンメトリックな形であるか否かを判定せよ」という問題です。
まず、自分のあまりイケてない解法から紹介したいと思います!

function isSymmetric(root: TreeNode | null): boolean {
  if (root === null || (root.right === null && root.left === null)) {
    return true;
  }
  if (root.right === null || root.left === null) {
    return false;
  }

  const left = getAllNodeLeft(root.left);
  const right = getAllNodeRight(root.right);

  if (left.length !== right.length) {
    return false;
  }

  for (let index = 0; index < left.length; index++) {
    if (left[index] !== right[index]) {
      return false;
    }
  }

  return true;
}

const getAllNodeLeft = (node: TreeNode | null): number[] => {
  if (node === null) {
    return [Infinity];
  }
  if (node.right === null && node.left === null) {
    return [node.val];
  }
  const left = getAllNodeLeft(node.left);
  const right = getAllNodeLeft(node.right);

  return [node.val, ...left, ...right];
};

const getAllNodeRight = (node: TreeNode | null): number[] => {
  if (node === null) {
    return [Infinity];
  }
  if (node.right === null && node.left === null) {
    return [node.val];
  }
  const left = getAllNodeRight(node.left);
  const right = getAllNodeRight(node.right);

  return [node.val, ...right, ...left];
};

コードの長さからイケてなさが伝わってきますね!😅
まず、方針としてはrootから左と右のNodeをそれぞれ探索していき、各Nodeの値を配列に入れていきます。そして、最終的に全ての値が入った配列を比較すして全て同じ値であればシンメトリックのはず!という感じですね!ポイントは、末端や途中で切れているNodeはnullとして扱うのは配列上難しいので数字のInfinityをnullの代わりに使ったことと、左が[2, 3]の時に右がシンメトリックであるなら[3, 2]となるため、返り値となる配列には順番を逆にして入れるの2つです。ただ、やはり配列に最終的な判定を委ねてしまっている点や、冗長さがある点などはイマイチ感があります…。
そこでSolutionを参照したのですが、以下のようなスマートなやり方があったので紹介します!

function isSymmetric(root: TreeNode | null): boolean {
  return isMirror(root, root);
}

function isMirror(t1: TreeNode | null, t2: TreeNode | null): boolean {
  if (t1 == null && t2 == null) return true;
  if (t1 == null || t2 == null) return false;
  return (
    t1.val == t2.val &&
    isMirror(t1.right, t2.left) &&
    isMirror(t1.left, t2.right)
  );
}

isMirror関数というものに根っことなるrootNodeを2つ渡しています。isMirrorは受け取った2つのNodeのいずれもがnullであれば同じタイミングで末端まで辿り着いた、すなわち同じとしてtrueを返し、違うタイミングでいずれかが末端に辿り着いたのであれば同じ形ではないとしてfalseを返します。また、returnにて現在の値と左右のNodeを比較していますが、そこでも自分の解答同様に一方のNodeの左と他方の右、一方の右と他方の左を比較しています。これは既に説明したようにシンメトリックな形は正反対になるからですね!というわけで、大まかな方向性としては探索途中に値が異なる場合、あるいは異なるタイミングで末端に辿り着いた場合はfalseとなり、そうでなく同時に末端に辿り着いた場合はtrueを返すというアルゴリズムとなっています!
自分の解法よりもこちらのほうが探索途中でfalseを返せるので早そうですし、コード的にもシンプルですね…。まだまだこの境地に至れていなかったので反省です😓

まとめ

Treesはやっていて難しいのですが楽しい問題が多いです!
自分は再帰関数が弱いと自認していたのですが、Treesの問題に取り組むことで後々紹介するDPあたりも再帰的なアプローチが以前よりも思いつくようになりました。楽しいだけではなく身になるのが、これらプログラミング問題の醍醐味であるとつくづく感じます。あとはAtCoderやLeetCode Contestの結果がついてくると万々歳なのですが…😅
とはいえこれまでの取り組みも決して無駄ではないはずなので、今週末のAtCoderとLeetCode Contestが少しでも良い結果になるよう頑張ります!