java非递归方法，使用堆栈查找二叉搜索树每个藤的所有节点

Question

我试图创建一种方法，在二叉搜索树中查找从根到每个叶的路径中的所有节点，并将它们存储在一个数组中。 到目前为止，我已经提出了一个很好的方法，如果根的右侧没有超过一个节点是两个节点的父节点，那么这个方法可以很好地工作。我花了很长时间才弄清楚到底是怎么回事，但如果我目前的方法是有效的，我必须了解这棵树，这太愚蠢了

这基本上就是我想做的：

输出：[[8, 3, 1],[8 ,3 ,6 ,4],[8, 3, 6, 7],[8, 10, 14, 13]]

我希望避免递归，而是使用堆栈。但我不知道如何“控制”从堆栈中弹出哪些节点。。如果他们有子树和子树呢

Answer 1

比如：

function Explore(node, currentPath)
   Add node to the currentPath

   If node has any Children
     If node has a left child
       Explore(left child, currentPath)
     if node has a right child  
       Explore(right child, currentPath)
   Else
     Node is a leaf node, report currentPath as a result.

   Remove the last node from currentPath
end

Answer 2

有关递归和迭代（使用堆栈）DFS实现，请参见Iterative DFS vs Recursive DFS and different elements order

编辑：

< >如果你忽略C++特定语法，这是非常可读的，但是这里有一个简短的伪代码描述。

create a stack of nodes
push root node of the tree on the stack. 
while (the stack is not empty) {
   pop the top of the stack, call it 'node' 
   if (we have not already marked 'node') {
     print the name of that node
     mark that node
     push any children of that node onto the stack
   } 
} 

递归方法中不需要的是一种跟踪已访问哪些节点的方法（这就是“标记”节点的意思）。这可以是节点本身的属性，也可以维护单独的数据结构。Java哈希集可以很好地实现这一点

Answer 3

http://en.wikipedia.org/wiki/Tree_traversal#Preorder

维基百科比我解释得更好。你需要深度优先遍历，当你碰到一片叶子时，记录到目前为止的整个路径