森田賢二のleetCodeの使い方、解説、解答を毎日更新しているキャラクター

[leetcode]問題解決と解説。110. Balanced Binary Tree [JavaScript]

[leetcode]問題解決。110. Balanced Binary Tree [JavaScript]

皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。
leetCodeの使い方や解説ではなく実際に問題を解決するために何をしたか
をメモ書きして行きます

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

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

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

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

森田賢二のleetCode
森田賢二のleetCode

110. Balanced Binary Tree ルール

ざっくり和訳

二分木が与えられたとき、それが高さバランス型かどうかを判定せよ。

この問題では、高さバランスのとれた二分木は次のように定義される。

すべてのノードの左と右の部分木の高さが1以下である二分木。

exampleは実際の問題ページを見てください

110. Balanced Binary Tree 問題ページ

110. Balanced Binary Tree

110. Balanced Binary Tree

my code is not good


function isBalanced(root){
 let arr = [root]
 if(root === null)return true
 let result = false , rightDepth = -1, leftDepth = -1
 while(arr.length > 0 && !result){
  let rightNode = arr[0].right 
  let leftNode = arr[0].left
  if(!!rightNode) arr.push(rightNode); rightDepth++
  if(!!leftNode) arr.push(leftNode); leftDepth++ 
  if(Math.abs(leftDepth - rightDepth) === 2) result = true
  arr.shift()
 }
 return result
};

 class TreeNode {
      val
      left
      right
      constructor(val, left, right) {
          this.val = (val===undefined ? 0 : val)
          this.left = (left===undefined ? null : left)
          this.right = (right===undefined ? null : right)
      }
 }

let rightRight = new TreeNode(7)
let rightLeft = new TreeNode(15)
let right = new TreeNode(20, rightLeft, rightRight)
let left = new TreeNode(9)
let root = new TreeNode(3, left, right)

isBalanced(root)

これは時間切れ

110. Balanced Binary Tree。discussの中の一つの解答例

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

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

これが違う実装

110. Balanced Binary Tree

1

110. Balanced Binary Treeをやってみて感想

  • WIP

カテゴリー leetCode