如何在不使用递归的情况下打印树的每个叶子路径。不用递归打印树的每个叶子路径
这是一个树，NOT二叉树
struct node {
int data
std::vector<node*> children;
}
打印所有的从根到叶的路径，即，以下是树
-------------root ------d m n ---x y z o p
结果应该是：
root-d-x root-d-y root-d-z root-m root-n-o root-n-p
我试图用非递归的方式，但失败了。
该策略很简单。往下走吧，然后起来。在每一点你都知道下一步该去哪里。
保留一个向量，它是您当前在树中的位置。从根开始。然后伪代码：
while True:
if not a leaf:
current_place.push_back(0) // move down one
else:
print current path.
while can't move right:
if at root:
exit()
current_place.pop_back() //move up one
current_place[-1] += 1
这些操作将需要函数调用。但它们是带有循环的函数调用，而不是递归，所以它不是递归的。
最后，它只是一个图表。有不同类型的图遍历。只需在堆栈中使用dfs，并打印没有前向边的节点。
完全没有回答这个问题...... –
public static void printAllPathToLeafNonRecursive(Node root) {
if (root == null) {
return;
}
Queue<Object> q = new LinkedList<Object>();
q.add(root);
q.add(root.data + "");
while(!q.isEmpty()){
Node head = (Node) q.poll();
String headPath = (String) q.poll();
if(head.isLeaf()){
System.out.println(headPath);
continue;
}
if(head.left!=null){
String leftStr = headPath + "->" + head.left.data;
q.add(head.left);
q.add(leftStr);
}
if(head.right!=null){
String rightStr = headPath + "->" + head.right.data;
q.add(head.right);
q.add(rightStr);
}
}
}
这是一个基于预先迭代遍历的Python解决方案，它使用堆栈。打印路径和路径。
class Stack(object): # just for reference
def __init__(self):
self.a = []
def push(self, b):
self.a.append(b)
def peek(self):
return self.a[-1]
def pop(self):
return self.a.pop()
def isEmpty(self):
return len(self.a) == 0
def show(self):
return self.a
def paths(troot): # you should create your own Tree and supply the root
current = troot
s = Stack()
s.push(current)
s.push(str(current.key))
s.push(current.key)
while not s.isEmpty():
pathsum = s.pop()
path = s.pop()
current = s.pop()
if not current.left and not current.right:
print 'path: %s, pathsum: %d' % (path, pathsum)
if current.right:
rightstr = path + "->" + str(current.right.key)
rightpathsum = pathsum * 10 + current.right.key
s.push(current.right)
s.push(rightstr)
s.push(rightpathsum)
if current.left:
leftstr = path + "->" + str(current.left.key)
leftpathsum = pathsum * 10 + current.left.key
s.push(current.left)
s.push(leftstr)
s.push(leftpathsum)
例如，对于下面的树：
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
1 7
/ \ / \
/ \ / \
/ \ / \
/ \ / \
0 2 5 8
/ \ / \ / \ / \
/ \ / \ / \ / \
NUL NUL NUL NUL 4 6 NUL 9
输出将是：
>>> paths()
path: 3->1->0, pathsum: 310
path: 3->1->2, pathsum: 312
path: 3->7->5->4, pathsum: 3754
path: 3->7->5->6, pathsum: 3756
path: 3->7->8->9, pathsum: 3789
public static void RoottoPathPrint(BinaryTreeNode root) {
Stack<Object> stack = new Stack<Object>();
if (root == null)
return;
stack.push(root.getData() + "");
stack.push(root);
while (!stack.isEmpty()) {
BinaryTreeNode temp = (BinaryTreeNode) stack.pop();
String path = (String) stack.pop();
if (temp.getRight() != null) {
stack.push(path + temp.getRight().getData());
stack.push(temp.getRight());
}
if (temp.getLeft() != null) {
stack.push(path + temp.getLeft().getData());
stack.push(temp.getLeft());
}
if (temp.getLeft() == null && temp.getRight() == null) {
System.out.println(path);
}
}
}
的想法是跟踪路径和节点两者的在我们遍历树的时候在一个堆栈中。对象堆栈负责照顾。 希望帮助！
private void rootToLeaf(BSTNode root){
Stack<Map<BSTNode,ArrayList<Integer>>> tmpStack = new Stack<Map<BSTNode,ArrayList<Integer>>>();
Map<BSTNode,ArrayList<Integer>> tmpMap = new HashMap<BSTNode,ArrayList<Integer>>();
//List<Integer> tmp_arraylist = new ArrayList<Integer>();
ArrayList<Integer> tmpList = new ArrayList<Integer>();
tmpList.add(root.data);
tmpMap.put(root, tmpList);
tmpStack.push(tmpMap);
while(!tmpStack.isEmpty()){
Map<BSTNode,ArrayList<Integer>> temp_map = tmpStack.pop();
for(BSTNode node : temp_map.keySet()){
if(node.getLeft()==null && node.getRight()==null){
for(int i: temp_map.get(node)){
System.out.print(i+" ");
}
System.out.println();
}
if(node.getRight()!=null){
ArrayList<Integer> tmp_List = new ArrayList<Integer>();
for(int i: temp_map.get(node)){
tmp_List.add(i);
}
tmp_List.add(node.getRight().getData());
Map<BSTNode,ArrayList<Integer>> tmphashMap = new HashMap<BSTNode,ArrayList<Integer>>();
tmphashMap.put(node.getRight(), tmp_List);
tmpStack.push(tmphashMap);
}
if(node.getLeft()!=null){
ArrayList<Integer> tmp_List = new ArrayList<Integer>();
for(int i: temp_map.get(node)){
tmp_List.add(i);
}
tmp_List.add(node.getLeft().getData());
Map<BSTNode,ArrayList<Integer>> tmphashMap = new HashMap<BSTNode,ArrayList<Integer>>();
tmphashMap.put(node.getLeft(), tmp_List);
tmpStack.push(tmphashMap);
}
}
}
}
对于n叉树 - DFS和BFS路径为基础，总结
100
// \ \
1 2 3 4
///// / \
10 11 12 13 14 40 41
/\
400 401
public void traverseDFS(Node root) {
Stack<Node> s = new Stack<Node>();
Stack<String> sPath = new Stack<>();
Stack<Integer> sSum = new Stack<>();
s.push(root); sPath.push(root.Id + ""); sSum.push(root.Id);
while (!s.isEmpty()) {
// Pop out
Node head = s.pop(); String headPath = sPath.pop(); Integer headSum = sSum.pop();
if(head.children == null || head.children.isEmpty()){ //Leaf
System.out.println(headPath + "(" + headSum+")");
continue;
}
for(Node child : head.children) {
String path = headPath + "->" + child.Id;
Integer sum = headSum + child.Id;
// Push on stack
s.push(child); sPath.push(path); sSum.push(sum);
}
}
}
public static void traverseBFS(Node root) {
Queue<Node> q = new LinkedList<>();
Queue<String> qPath = new LinkedList<>();
Queue<Integer> qSum = new LinkedList<>();
q.add(root); qPath.add(root.Id + ""); qSum.add(root.Id);
while(!q.isEmpty()){
// Poll the q
Node head = q.poll(); String headPath = qPath.poll(); Integer headSum = qSum.poll();
if(head.children == null || head.children.isEmpty()){ //Leaf
System.out.println(headPath + "(" + headSum+")");
continue;
}
for(Node child : head.children) {
String path = headPath + "->" + child.Id;
Integer sum = headSum + child.Id;
// Add to the q
q.add(child); qPath.add(path); qSum.add(sum);
}
}
}
class Node {
int Id;
String Data;
Node Parent;
ArrayList<Node> children;
public Node(int id, String data) {
Id = id;
Data = data;
}
}
输出
-----------Depth FS-------------
100->4->41(145)
100->4->40->401(545)
100->4->40->400(544)
100->3(103)
100->2(102)
100->1->14(115)
100->1->13(114)
100->1->12(113)
100->1->11(112)
100->1->10(111)
-----------BFS-------------
100->2(102)
100->3(103)
100->1->10(111)
100->1->11(112)
100->1->12(113)
100->1->13(114)
100->1->14(115)
100->4->41(145)
100->4->40->400(544)
100->4->40->401(545)
这是功课？ – benjer3
我相信你可以调整你的情况的非递归二叉树遍历。具有最小内存开销的最简单的实现将在'节点'中具有父节点指针。请参阅[nonRecursiveInOrderTraversal（）]（http://en.wikipedia.org/wiki/Tree_traversal）。 –