J'essaie d'accomplir quelque chose qui semble simple mais avoir du mal à la mettre en œuvre. Compte tenu d'un arbre binaire et d'un nœud, renvoyez le chemin. Je l'ai tenté ci-dessous mais je suis vraiment coincé. Je ne suis pas tout à fait sûr de savoir comment sortir de la fonction récursive une fois que je trouve le nœud cible.
p>
const tree = {
val: 3,
left: {
val: 5,
left: {
val: 6,
left: null,
right: null
},
right: {
val: 2,
left: null,
right: null
}
},
right: {
val: 1,
left: null,
right: null
}
};
const findPathFromRoot = (currentNode, targetNode, path) => {
path + currentNode.val;
if (currentNode === targetNode) {
return path + targetNode.val;
}
findPathFromRoot(currentNode.left, targetNode, path);
findPathFromRoot(currentNode.right, targetNode, path);
}
const target = tree.left.right;
console.log(findPathFromRoot(tree, target, '')); // should return "352"3 Réponses :
Comme mentionné dans les commentaires, si votre arbre a été trié, cela pourrait être effectué plus rapidement.
tel quel, chaque nœud doit être vérifié. P>
Vous étiez presque là avec ce que vous avez tenté, d'abord Vous devez vérifier si vous avez un nœud gauche ou droit, puis je vérifie le nœud gauche, si cela trouve le nœud Down Down Cet arborescence est revenir, s'il ne le fera pas, il n'essaiera pas le bon nœud. Cela fait cela de manière récursive pour que chaque nœud possible soit visité. P>
ci-dessous est un exemple de travail .. p>
p>
const tree = {
val: 3,
left: {
val: 5,
left: {
val: 6,
left: null,
right: null
},
right: {
val: 2,
left: null,
right: null
}
},
right: {
val: 1,
left: null,
right: null
}
};
const findPathFromRoot = (currentNode, targetNode, path) => {
path += currentNode.val;
if (currentNode === targetNode) {
return path;
}
let ret = null;
if (currentNode.left) ret = findPathFromRoot(currentNode.left, targetNode, path);
if (currentNode.right && !ret) ret = findPathFromRoot(currentNode.right, targetNode, path);
return ret;
}
const target = tree.left.right;
console.log(findPathFromRoot(tree, target, '')); // should return "352"Ah c'est cool. Nous n'avons donc pas à vérifier le bon sous-arbre si le nœud cible est dans le sous-arbre de gauche? Cela signifie que nous pourrions avoir pour ne pas avoir à vérifier chaque nœud?
Vous devez mettre en logique pour décider de voyager à gauche ou à partir de la valeur du nœud actuel et appelez votre méthode avec le courantNode.Left ou CurrentNode.right en fonction de cette logique. Ensuite, rendez-vous soit lorsque vous obtenez une valeur nulle (cela signifie que la cible n'existe pas dans l'arborescence) ou de retourner lorsque la cible actuelleNode.Value ===.
Il y a aussi un problème avec votre arborescence, toutes les valeurs à gauche de votre racine doivent être plus grandes que la valeur de la racine et toutes les valeurs à droite de la racine doivent être plus petites, mais on dirait que le 2 est à gauche de la racine (quelle valeur est 3).
const findPathFromRoot = (root, target, path = "") => {
if (root === null) {
return null;
}
path = path + root.val;
if (root === target) {
return path;
}
const left = findPathFromRoot(root.left, target, path);
const right = findPathFromRoot(root.right, target, path);
return left || right;
};
Why does this work?Return statement always returns to the caller, in your case you are returning only when you find the target is found which in turn returns back to one of findPathFromRoot(currentNode.left, ...) or findPathFromRoot(currentNode.right, ...). But these don't return themselves. So the fix to your code is to return if you find the target either in your left or the right subtree.
Au début, je pensais que cela ressemblait à une structure de type d'arbre binaire triée, mais cela ne semble pas être .. par exemple.
2 <3 nous allons donc aller à gauche, (bien ici) ,.. Ensuite, nous avons2 <5 , allez à gauche, mais nous en avons 6, pas 2. donc parce que Ceci n'est pas trié le seul moyen que vous puissiez faire cela est de visiter chaque nœud. Est-ce que ça va? Si les 6 et 2 ont été échangés, nous pourrions binaires hacher ..Oui, ce n'est pas un arbre de recherche binaire.