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