算法 - 如何不用遞歸 列出 樹（多叉） 中根節點到葉節點的所有路徑（Java）

問題描述

比如，對于下面這個二叉樹，它所有的路徑為：

8 -> 3 -> 1

8 -> 2 -> 6 -> 4

8 -> 3 -> 6 -> 7

8 -> 10 -> 14 -> 13

怎么用Java去實現？

問題解答

不用遞歸的話，那就深度優先啦！采用棧， 首先將根結點壓入棧，如果棧不為空，而后出棧并輸出當前結點中值，而后先把右子樹壓入棧，再把左子樹壓入棧，再判斷棧是否為空，循環.....步驟如下: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'); } 回答2：

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

深度優先？。。

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