再帰アルゴリズムを練習するためにLEETCodeで再帰問題を探しました!

初心者ですが、20分以内にこの問題を解決できると思いますので、Easyの難易度で83%に達するRange Sum of BST問題を試してみることにしました.

私の予想は外れて、1時間半ぐらい口ずさんだ.
でもちょうど入門しようと思った時に簡単な木探索問題に遭遇したのが良かったです.
問題は簡単だ.
与えられた非線形データパスのサブノードに戻り、LowとHighの間にすべてのサブノードの値(LowとHighを中間に加算)を加算します.
Rootは下図のようにrootです.valとrootがあります左はrootval未満の値はrootです.右はルートvalより大きい値が含まれます.(またはnull)

最初は別の場所で尻尾耳で解くのが楽そうで、尻尾耳で解くために

return (left 탐색) + (right 탐색)

同じような
最後の再帰呼び出しでは,前回に値を渡す部分がブロックされているので,まず簡単に問題を解決することにした.
.

1.カウント値

let count = 0

カウントする変数を設定します.
.

2.該当する値の検索

if文で条件に合致するかどうかを判断します.

if ( root.val <= high && root.val >= low ) { 
	console.log('더하자! ', root.val)
	count += root.val 
	}

ルートの場合.val値がlowとhighの間にある場合は条件に合致するためcountではrootとなる.もっとvalをつけよう
.

3.左右のナビゲーション

左利きや右利きも同様に探索し、対応する値があるかどうかを見てみましょう.

    // left가 null이 아니라면 left 탐색
    if ( root.left != undefined ) { 
        console.log('왼쪽 탐색')
        count += rangeSumBST(root.left , low , high) 
        }
    
    // right도 똑같이 해줌
    if ( root.right != undefined ) { 
        console.log('오른쪽 탐색')
        count += rangeSumBST(root.right , low , high) 
        }
    

注記で説明したように、左または右が定義されていない場合は、ブラウズを試みます.
rootだからvalがundefined時のlow、high間の値なのか、ifターン時にエラーが発生したからです.
また、そうでなくても、定義されていない値のために関数を呼び出してスタックを積み上げる必要がなく、メモリの浪費を防止することができる.

実行

したがって、最終的なコード形式は次のとおりです.

function rangeSumBST(root: TreeNode | null, low: number, high: number ): number {
    console.log('현재값 ',root.val)

    let count = 0
    
    // low, high 사이의 값이라면 count에 root.val을 더함
    if ( root.val <= high && root.val >= low ) { 
        console.log('더하자! ', root.val)
        count += root.val }
    
    // left가 null이 아니라면 left 탐색
    if ( root.left != undefined ) { 
        console.log('왼쪽 탐색')
        count += rangeSumBST(root.left , low , high) }
    
    // right도 똑같이 해줌
    if ( root.right != undefined ) { 
        console.log('오른쪽 탐색')
        count += rangeSumBST(root.right , low , high) }
    
    
    return count
};

最初の条件.
root = [10,5,15,3,7,null,18]
low = 7
high = 15
で、上のコードを振り返ると、コンソールが次のように表示されます.

현재값  10
더하자!  10
왼쪽 탐색
현재값  5
왼쪽 탐색
현재값  3
오른쪽 탐색
현재값  7
더하자!  7
오른쪽 탐색
현재값  15
더하자!  15
오른쪽 탐색
현재값  18

まず対応する初期ルート.val in 10をカウントに加算すると、左から右へのナビゲーションが表示されます.
初めて試した時に10万返したのはなぜかと思います.
左、右のナビゲーションでcount+=は無視されます.
countは返され、追加されず、countは増加しません.
現在,再帰を用いるとともに,結果値を前の再帰部分に明確に渡すことはできない.
コードをもう一度読んで、次はいくつかの再帰的な問題をします.