Imprimer tous les chemins de la racine à chaque feuille

Vous pouvez utiliser la récursivité avec un générateur:

[[1, 2, 4, 7], [1, 2, 5], [1, 3, 6]]

Sortie:

def get_paths(d, _c = []):
  val, _l, _r = d
  if _l is None and _r is None:
    yield [*_c, val]
  if _l is not None:
    yield from get_paths(_l, _c = _c+[val])
  if _r is not None:
    yield from get_paths(_r, _c = _c+[val])

print(list(get_paths((1,(2,(4,(7,None,None),None),(5, None, None)),(3,None,(6, None,None))))))

On dirait que vous essayez de résoudre ce problème: https://leetcode.com/ problèmes / chemins-d'arbre-binaire /

Ici, vous pouvez simplement commencer à explorer l'arbre avec dfs et stocker les valeurs au fur et à mesure que vous descendez dans l'arbre et maintenir un vecteur de toutes les valeurs de la racine au nœud actuel. Dès que vous avez terminé de traiter ce nœud, supprimez simplement les valeurs du nœud actuel de ce vecteur. Lorsque nous avons atteint le nœud feuille, nous ajoutons simplement les valeurs en vecteur à notre réponse.

Voici le code implémenté dans cpp pour votre référence:

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
 public:
   void solve(TreeNode* root, vector<int>&values, vector<string>&ans) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        // leaf node
        string str = "";
        values.push_back(root->val);
        str += ::to_string(values[0]);
        for (int i = 1; i < values.size(); ++i) {
            str += "->";
            str += ::to_string(values[i]);
        }
        ans.push_back(str);
        values.pop_back();
        return;
    }
    values.push_back(root->val);
    solve(root->left, values, ans);
    solve(root->right, values, ans);
    values.pop_back();
  }
 vector<string> binaryTreePaths(TreeNode* root) {
    vector<int>values;
    vector<string>ans;
    solve(root,values,ans);
    return ans;
  }
};

p >

Voici un générateur récursif plus lisible:

def paths(node):
    if node is None:
        return
    val, *children = node
    if any(children):
        for child in children: 
            for path in paths(child):
                yield [val] + path
    else:
        yield [val]

>>> list(paths(root))
[[1, 2, 4, 7], [1, 2, 5], [1, 3, 6]]

Ceci a l'avantage supplémentaire de travailler pour des nœuds avec un nombre arbitraire d'enfants.