算法 - 如何不用递归 列出 树（多叉） 中根节点到叶节点的所有路径（Java）

问题描述

比如，对于下面这个二叉树，它所有的路径为：

8 -> 3 -> 1

8 -> 2 -> 6 -> 4

8 -> 3 -> 6 -> 7

8 -> 10 -> 14 -> 13

怎么用Java去实现？

问题解答

不用递归的话，那就深度优先啦！采用栈， 首先将根结点压入栈，如果栈不为空，而后出栈并输出当前结点中值，而后先把右子树压入栈，再把左子树压入栈，再判断栈是否为空，循环.....步骤如下:1) 先把二叉树的根结点入栈2)判断栈是否为空，不为空，则出栈，并输出出栈树结点的值3)出栈树结点的右子树入栈4)出栈树结点的左子树入栈5)循环回到(2)这是我之前看到的一个方法，不知道能不能帮到题主？

public void depthOrderTraversal(){ if(root==null){ System.out.println('empty tree'); return; } ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>(); stack.push(root); while(stack.isEmpty()==false){ TreeNode node=stack.pop(); System.out.print(node.value+' '); if(node.right!=null){ stack.push(node.right); } if(node.left!=null){ stack.push(node.left); } } System.out.print('n'); } 回答2：

用栈替代递归：https://zh.coursera.org/learn...

深度优先？。。

使用广度优先遍历，然后状态中储存该节点的所有父节点，到叶子节点后输出。