[leetcode]問題解答と解説。100. Same Tree [JavaScript]

皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。

私はある決意をして今臨んでいます。
モチベーションを保つためだけにこれをやっています。

では今日のleetCode。
「100. Same Tree」の解決策と方法。自分がまず挑戦して
やったことをさらけ出します。

※下にある自分のコードは自分で設けた制限時間内に書けたところまです。

これは
「私は年末までこれを続けたらどんなleetCoderになるか」のシリーズ。
実験的ブログ更新です。

森田賢二のleetCode

100. Same Tree ルール

ざっくり和訳

100. Same Tree 問題ページ

100. Same Tree

100. Same Tree

my code is time over.

/**
 * 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 isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    let isSame = false;
    if(p.val === q.val){
        if(p.left.val && q.left.val){
               return isSameTree(p.left.left, q.left.left)
        }
        if(p.right.val && q.right.val){
            return isSameTree(p.right.right, q.right.right)
        }
    }
    return isSame
};

function isSameTree(p, q) {
    if(q !== null && p !== null || p?.val !== q?.val) return false
    const left = isSameTree(p?.left, q?.left)
    const right = isSameTree(p?.right, q?.right)
    if(!left || !right) return false
    return true
};

タイムオーバーで撃沈

100. Same Tree。discussの中の一つの解答例

数ある中からJavaScriptのもので、理解しやすい解説をピックアップしました。
discussから見ればさらにもっと違う方法で真似したくなるものがあるかもしれないですね

JavaScriptでfilterされている、discussはこちらから

100. Same Tree

1. 再帰的

function isSameTree(p, q) {
  if (!p && !q) return true; // 両方ともfalsy(null)だったら続ける
  if (!p || !q || p.val !== q.val) return false;  // どちらかが同値じゃないfalseの条件

  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

2. queue

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  const queue = [p, q];
  while (queue.length > 0) {
    const first = queue.shift();
    const second = queue.shift();

    if (!first && !second) continue; // 両方ともfalsy(null)だったら続ける
    if (!first || !second || first.val !== second.val) return false; // どちらかが同値じゃないfalseの条件

    queue.push(first.left);
    queue.push(second.left);
    queue.push(first.right);
    queue.push(second.right);
  }

  return true;
}

2.ネタ回答

https://leetcode.com/problems/same-tree/discuss/607631/Javascript-TOO-EASY

var isSameTree = function(p, q) {
     return JSON.stringify(p)===JSON.stringify(q)
};

100. Same Treeをやってみて感想

カテゴリー leetCode