日常アルゴリズムのパスの合計について話す

[[426794]]

この記事はWeChatの公開アカウント「3分でフロントエンドを学ぶ」から転載したもので、著者はsisterAnです。この記事を転載する場合は、「3分で学ぶフロントエンド」公式アカウントまでご連絡ください。

木の基礎については、こちらをご覧ください: 初心者のための木

バイナリ ツリーとターゲットの合計が与えられた場合、ツリー内のルート ノードからリーフ ノードへのパスが存在するかどうか、およびこのパス上のすべてのノード値の合計がターゲットの合計と等しいかどうかを判断します。

注: リーフ ノードは子ノードを持たないノードです。

例: 次の二分木があり、目標の合計が 22 の場合、

   5
     / \
    4 8
   // \
  11 13 4
 / \ \
 7 2 1

ルート ノードからリーフ ノードへのパス 5->4->11->2 があり、ターゲットの合計が 22 であるため、true を返します。

解決：

ツリー全体を横断するだけ

現在のノードがリーフ ノードでない場合は、そのすべての子ノードを再帰的に処理し、渡されるパラメーターは合計から現在のノード値を引いた値になります。

現在のノードがリーフ ノードの場合、パラメーターの合計が現在のノード値と等しいかどうかを判断します。等しい場合は true を返し、そうでない場合は false を返します。

コード実装:

 var hasPathSum =関数(ルート、合計) {
  // ルートノードは空です
  (ルート === null )の場合、戻り値 間違い; 
   
  // リーフノードと合計パラメータはリーフノードの値に等しい
  root.left === null && root.right === nullの場合、 root.val === sumを返します。 
 
  // 合計から現在の値を減算し、再帰します
合計=合計- ルート.val
 hasPathSum(root.left , sum ) || hasPathSum(root.right , sum )を返します。
 };

解決：

ツリー全体を横断するだけ

• 現在のノードがリーフ ノードでない場合は、そのすべての子ノードを再帰的に処理し、渡されるパラメーターは合計から現在のノード値を引いた値になります。
• 現在のノードがリーフ ノードの場合、パラメーターの合計が現在のノード値と等しいかどうかを判断します。等しい場合は true を返し、そうでない場合は false を返します。

コード実装:

 var hasPathSum =関数(ルート、合計) {
  // ルートノードは空です
  (ルート === null )の場合、戻り値 間違い; 
   
  // リーフノードと合計パラメータはリーフノードの値に等しい
  root.left === null && root.right === nullの場合、 root.val === sumを返します。 
 
  // 合計から現在の値を減算し、再帰します
合計=合計- ルート.val
 hasPathSum(root.left , sum ) || hasPathSum(root.right , sum )を返します。
 };

リートコード: https://leetcode-cn.com/problems/path-sum/solution/javascript-lu-jing-zong-he-by-user7746o/