リーフルートの数への合計は、アマゾンのインタビューの質問を解決する

質問:0 - 9だけからの数字を含んでいる2進木を与えられて、葉ルートへの各々のルートは、数を表すことができました.
例として、123番を表すルートツーリーフパス1 -> 2 -> 3を示します.
葉の数にすべてのルートの合計金額を表示して下さい.
EG :

         1
        / \
       2   3

上の木に
パス1 = 1 -> 2 = 12
パス2 = 1 -> 3 = 13
出力は12 + 13 = 25になります
質問を読むだけで、我々は木を横断しなければならないと言うことができます、しかし、我々は親-子関係が維持されるそのような方法で横断しなければなりません.
深さの最初の横断は、ノードを選択し、バックトラッキングの前に、各枝に沿って可能な限り探索します.
ウィキペディアからのアニメーション

コードへの変換

   dfs(node){
       if(node == null) return;

       // do something

       dfs(node.left);
       dfs(node.right);
   }

次に、現在のノードで値を処理する方法について説明します.
このような

  dfs(node,prev){
      if(node == null) return;

      let curr = prev * 10 + node.val;

      dfs(node.left,curr);
      dfs(node.right,curr);

コールスタックについて
ここでは、再帰的にDFSを呼び出しているので、それぞれの呼び出しに対して別々のコールスタックが維持され、ルートの現在のノード値を追跡し、別の呼び出しスタックに存在するため、他のノードのルート->ノード値に干渉しません.最後にアニメーションを参照してください.
最後の障害は計算値を返す方法です.
私たちは葉ノードが左右の子がNULLであるノードであることを知っています.そして、それは特定のサブツリー経路のためにルート->葉値を返す我々の手掛かりです.

    if(root.left == null && root.right == null) 
       return prev*10 + node.val;

内部ノードに遭遇すると、左と右のサブツリーから返される値を追加し、それを返します.

     return dfs(root.left,curr) + return dfs(root.right,curr);

各ステップの可視化

すべてをコードにまとめる

var sumNumbers = function(root) {
    return dfs(root,0);
};

function dfs(node,prev){
    if(node == null) return 0;
    if(node.left == null && node.right == null){
        return prev*10 + node.val;
    }

    let curr = prev*10 + node.val;

    return dfs(node.left,curr) + dfs(node.right,curr);
}

あなたが私の説明が好きだったら
ギタブ:https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/rootToleaf.js