当前位置:C++技术网 > 资讯 > 数据结构笔记分享:35 在二叉树中找出和为某一值的所有路径

数据结构笔记分享:35 在二叉树中找出和为某一值的所有路径

更新时间:2016-01-28 19:25:50浏览次数:1+次

  没有了递归 当然想到递归转换的另外的方法——栈


  我们需要一个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();
}