没有了递归 当然想到递归转换的另外的方法——栈
我们需要一个Stack,来保存访问过的节点,即在对该节点的递归前让其进栈,对该节点的递归结束后,再让其出栈——深度优先原则(DFS)。
此外,在递归中,如果发现某节点(及其路径)符合条件,如何从头到尾打印是比较头疼的,因为DFS使用的是stack而不是queue,为此我们需要一个临时栈,来辅助打印。
static void FindBinNode(BinNode root, intsum, Stack stack)
{
if (root == null)
return;
stack.Push(root.Element);
//Leaf
if (root.IsLeaf())
{
if (root.Element == sum)
{
Stack tempStack = new Stack();
while (stack.Count > 0)
{
tempStack.Push(stack.Pop());
}
while (tempStack.Count > 0)
{
Console.WriteLine(tempStack.Peek());
stack.Push(tempStack.Pop());
}
Console.WriteLine();
}
}
if (root.Left != null)
FindBinNode(root.Left, sum - root.Element, stack);
if (root.Right != null)
FindBinNode(root.Right, sum - root.Element, stack);
stack.Pop();
}