打印树的每个叶子路径而不递归

Question

如何在不使用递归的情况下打印树的每个叶子路径.

它是一棵树,而不是二叉树

struct node {
    int data
    std::vector<node*> children;
}

打印从根到叶的所有路径,即以下是树

• r:是根节点
• d,m,n是r的孩子
• x,y,z是儿童
• 米没有孩子
• o,p是n的孩子

-------------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

我尝试使用非递归方式但失败了.

Answer 1

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);
        }
    }


}

Answer 2

这是一个纯粹基于使用堆栈的预迭代遍历的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

Answer 3

策略很简单。向下，向右，然后向上。在每个点上，您都知道下一步该去哪里。

保留一个向量，它是你在树中当前的位置。从根开始。然后用伪代码：

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

这些操作将需要函数调用。但它们是带有循环的函数调用，而不是递归，所以它不是递归的。