問(wèn)題描述

比如，對(duì)于下面這個(gè)二叉樹(shù)，它所有的路徑為：

8 -> 3 -> 1

8 -> 2 -> 6 -> 4

8 -> 3 -> 6 -> 7

8 -> 10 -> 14 -> 13

怎么用Java去實(shí)現(xiàn)？

問(wèn)題解答

不用遞歸的話(huà)，那就深度優(yōu)先啦！采用棧， 首先將根結(jié)點(diǎn)壓入棧，如果棧不為空，而后出棧并輸出當(dāng)前結(jié)點(diǎn)中值，而后先把右子樹(shù)壓入棧，再把左子樹(shù)壓入棧，再判斷棧是否為空，循環(huán).....步驟如下:1) 先把二叉樹(shù)的根結(jié)點(diǎn)入棧2)判斷棧是否為空，不為空，則出棧，并輸出出棧樹(shù)結(jié)點(diǎn)的值3)出棧樹(shù)結(jié)點(diǎn)的右子樹(shù)入棧4)出棧樹(shù)結(jié)點(diǎn)的左子樹(shù)入棧5)循環(huán)回到(2)這是我之前看到的一個(gè)方法，不知道能不能幫到題主？

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...

深度優(yōu)先？。。

使用廣度優(yōu)先遍歷，然后狀態(tài)中儲(chǔ)存該節(jié)點(diǎn)的所有父節(jié)點(diǎn)，到葉子節(jié)點(diǎn)后輸出。