algorithm - 不递归地打印树的每个叶子路径

Question

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

它是一棵树，不是二叉树

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

打印从根到叶的所有路径，即下面是树

• r:为根节点
• d, m, n 是 r 的 child
• x,y,z 是 d 的 child
• m没有 child
• o, p是n的 child

-------------root------d         m          n---x  y  z              o  p

结果应该是:

root-d-xroot-d-yroot-d-zroot-mroot-n-oroot-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);
        }
    }


}