我正在尝试创建一种方法，该方法将在二叉搜索树中查找从根到每个叶子的路径中的所有节点并将它们存储在数组中。到目前为止，如果根的右侧没有多个作为两个节点的父节点的节点，我已经提出了一种可笑的方法。我花了很长时间才弄清楚出了什么问题，但如果我目前的方法是有效的，我必须知道这棵树，那太愚蠢了。
这基本上是我想要做的：
输出：[[8, 3, 1],[8 ,3 ,6 ,4],[8, 3, 6, 7],[8, 10, 14, 13]]
我想避免递归，而是使用堆栈。但我不知道如何“控制”从堆栈中弹出哪些节点。如果它们有子树和子树怎么办。
像这样的东西：
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
请参阅迭代 DFS 与递归 DFS 以及递归和迭代（使用堆栈）DFS 实现的不同元素顺序。
编辑：
如果您忽略 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 HashSet 可以很好地解决这个问题。
如果您不打算进行递归，则必须将调用完成位置或递归解决方案中的局部变量所暗示的数据类型显式存储在堆栈中。在这种情况下，我使用了几个布尔值来指示左子树是否已完成以及右子树是否已完成。
我不能完全让自己用一种方法来做这一切。我确实使用单独的方法从堆栈中提取节点标签列表。此外，为了节省携带单独的标签列表，我并没有将其严格视为堆栈。我认为使其成为严格堆栈的更改相当明显。我只评论了核心代码。随意询问是否还有其他不清楚的地方。
我确实想强调这不是我推荐的设计。我会使用递归，我认为这会导致更简单的代码。我也没有花很多时间打磨它。
import java.util.Stack;
public class Bad {
public static void main(String[] args) {
TreeNode root;
boolean firstLeaf = true;
root = makeTree();
Stack<StackNode> stack = new Stack<StackNode>();
stack.push(new StackNode(root));
System.out.print("[");
while (stack.size() > 0) {
// Decide what to do next with the top element
StackNode top = stack.lastElement();
if (top.tn == null) {
// Nothing to do for a null subtree
stack.pop();
} else {
if (top.tn.left == null && top.tn.right == null) {
// leaf element, print it out and pop it.
if(!firstLeaf) {
System.out.print(",");
}
firstLeaf = false;
System.out.print("[" + getLabelList(stack) + "]");
stack.pop();
} else {
if (top.leftDone) {
if (!top.rightDone) {
stack.push(new StackNode(top.tn.right));
top.rightDone = true;
} else {
// Done both subtrees
stack.pop();
}
} else {
stack.push(new StackNode(top.tn.left));
top.leftDone = true;
}
}
}
}
System.out.println("]");
}
private static class StackNode {
TreeNode tn;
boolean leftDone;
boolean rightDone;
public StackNode(TreeNode tn) {
this.tn = tn;
}
}
private static String getLabelList(Stack<StackNode> in) {
String result = "";
for (StackNode node : in) {
if (result.length() > 0) {
result += ", ";
}
result += node.tn.label;
}
//System.out.print("getLabelList: " + result);
return result;
}
private static TreeNode makeTree() {
TreeNode l;
TreeNode r;
l = new TreeNode(4, null, null);
r = new TreeNode(7, null, null);
r = new TreeNode(6, l, r);
l = new TreeNode(1, null, null);
l = new TreeNode(3, l, r);
r = new TreeNode(14, new TreeNode(13, null, null), null);
r = new TreeNode(10, null, r);
return (new TreeNode(8, l, r));
}
}
class StackNode {
TreeNode current;
boolean leftSubtreeDone;
}
class TreeNode {
int label;
TreeNode left;
TreeNode right;
public TreeNode(int label, TreeNode left, TreeNode right) {
this.label = label;
this.left = left;
this.right = right;
}
}
http://en.wikipedia.org/wiki/Tree_traversal#Preorder
维基百科对它的解释比我以往任何时候都好。你想要深度优先遍历，当你碰到一片叶子时，记录到目前为止所走的整个路径。