Binäre Baumpfade - was ist mit meinem Code falsch?

Question

Hier ist das Problem der binären Baumpfade: Gegeben eine binäre Struktur, alle Wurzel-zu-Blatt-Pfade zurückgeben.

Zum Beispiel angesichts der folgenden binären Baum:

1 
/ \ 
2  3 
\ 
    5 

Alle Wurzel-zu-Blatt Pfade sind:

["1->2->5", "1->3"] 

Und hier ist mein Javascript-Code:

/** 
* Definition for a binary tree node. 
* function TreeNode(val) { 
*  this.val = val; 
*  this.left = this.right = null; 
* } 
*/ 
/** 
* @param {TreeNode} root 
* @return {string[]} 
*/ 
var binaryTreePaths = function(root) { 
    var paths = []; 
    if(!root) return []; 
    if(root.left == null && root.right == null){ 
     if(paths.length == 0) return [""+root.val]; 
     else return root.val; 
    } 
    else{ 
     if(root.left) paths.push(root.val + "->" + binaryTreePaths(root.left)) 
     if(root.right) paths.push(root.val + "->" + binaryTreePaths(root.right)) 
    } 

    return paths; 
}; 

Testfall:

Eingang:

[1,2,3,5,6] 

Ausgang:

["1->2->5,2->6","1->3"] 

Erwartet:

["1->2->5","1->2->6","1->3"] 

Warum mein Code der ausgegeben nicht den vollständigen Pfad der Rückkehr "1-> 2-> 6"?

Answer 1

Wenn Sie einen rekursiven Aufruf ausführen, gibt Ihre Funktion ein Array zurück. Sie können nicht einfach die Verkettung dieses Arrays mit der Präfix-Zeichenfolge pushen; Sie müssen durch jede der zurück Subpfade iterieren und einen separaten Pfad bauen auf das Array schieben:

var binaryTreePaths = function(root) { 
    var paths = []; 
    if(!root) return []; 
    if(root.left == null && root.right == null){ 
     if(paths.length == 0) return [""+root.val]; 
     else return root.val; 
    } 
    else{ 
     if(root.left) 
      binaryTreePaths(root.left).forEach(function(lp) { 
      paths.push(root.val + "->" + lp); 
      }); 
     if(root.right) 
      binaryTreePaths(root.right).forEach(function(rp) { 
      paths.push(root.val + "->" + rp); 
      }); 
    } 

    return paths; 
};