算法 - 如何不用递归 列出 树（多叉） 中根节点到叶节点的所有路径（Java）

Question

比如，对于下面这个二叉树，它所有的路径为：

8 -> 3 -> 1

8 -> 2 -> 6 -> 4

8 -> 3 -> 6 -> 7

8 -> 10 -> 14 -> 13

怎么用Java去实现？

Answer 1

Si vous n'avez pas besoin de récursivité, utilisez d'abord la profondeur !
À l'aide d'une pile, poussez d'abord le nœud racine sur la pile. Si la pile n'est pas vide, sortez-la et affichez la valeur médiane du nœud actuel. Ensuite, poussez d'abord le sous-arbre droit sur la pile, puis poussez-le. le sous-arbre de gauche sur la pile. , puis jugez si la pile est vide, bouclez...
Les étapes sont les suivantes :
1) Mettez d'abord le nœud racine de l'arbre binaire dans la pile
2) Déterminez si la pile est vide, et si elle n'est pas vide, alors éclatez la pile et affichez la valeur du nœud d'arbre éclaté
3) Poussez le sous-arbre droit du nœud d'arbre éclaté sur la pile
4 ) Poussez le sous-arbre gauche du nœud de l'arbre éclaté sur la pile
5) Bouclez vers (2)
C'est une méthode que j'ai déjà vue. Je me demande si elle peut aider le questionneur ?

public void depthOrderTraversal(){  
        if(root==null){  
            System.out.println("empty tree");  
            return;  
        }         
        ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();  
        stack.push(root);         
        while(stack.isEmpty()==false){  
            TreeNode node=stack.pop();  
            System.out.print(node.value+"    ");  
            if(node.right!=null){  
                stack.push(node.right);  
            }  
            if(node.left!=null){  
                stack.push(node.left);  
            }             
        }  
        System.out.print("\n");  
    }  

Answer 2

Remplacez la récursivité par stack : https://zh.coursera.org/learn...

Answer 3

La profondeur d'abord ? . .

Answer 4

Utilisez le parcours en largeur d'abord, puis stockez tous les nœuds parents du nœud dans l'état et affichez-le après avoir atteint le nœud feuille.