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

Question

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

8 -> 3 -> 1

8 -> 2 -> 6 -> 4

8 -> 3 -> 6 -> 7

8 -> 10 -> 14 -> 13

怎么用Java去实现？

Answer 1

不用遞歸的話，那就深度優先！
採用棧， 先將根結點壓入棧，如果棧不為空，而後出棧並輸出當前結點中值，而後先把右子樹壓入棧，再把左子樹壓入棧，再判斷棧是否為空，循環.....
步驟如下:
1) 先把二元樹的根結點入棧
2)判斷棧是否為空，不為空，則出棧，並輸出出棧樹結點的值
3)出棧樹結點的右子樹入棧
4)出棧樹結點的左子樹入棧
5)循環回到(2)
這是我之前看到的一個方法，不知道能不能幫到題主？

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

用棧替代遞歸：https://zh.coursera.org/learn...

Answer 3

深度優先？ 。 。

Answer 4

使用廣度優先遍歷，然後狀態儲存該節點的所有父節點，到葉子節點後輸出。