java - 在java中打印BST中的所有路径

Question

BST 中的路径是从根节点到叶节点的一次遍历。因此，如果我们有一个以下形式的二叉树，

   7
 3   9
1 5 8 13

路径是，

7 3 1 
7 3 5 
7 9 8 
7 9 13 

这是我的代码，无法正常工作。

public void printPath(Node root){
        Deque<Node> stack = new ArrayDeque<>();
        printPath(root, stack);


    }

    public void printPath(Node root, Deque<Node> stack){

        if(root == null){
            Iterator itr = stack.descendingIterator();
            while(itr.hasNext()){
                Node p = (Node) itr.next();
                System.out.print(p.data + " ");
            }
            stack.poll();
            System.out.println();
            return;
        }
        stack.offerFirst(root);
        printPath(root.left, stack);
        printPath(root.right, stack);

    }

此代码未正确打印所有路径。任何帮助表示赞赏。

Answer 1

基于预序遍历的稍微更加自记录的解决方案。这应该适用于二叉树(不需要 BST):

public class BTPaths {
    private static final class BST<T> {
        final T key;
        BST<T> left;
        BST<T> right;

        BST(T key) {
            this.key = key;
        }
    }

    public static void main(String[] args) {
        BST<Integer> t = new BST<>(100);
        t.left = new BST<>(50);
        t.right = new BST<>(150);
        t.left.right = new BST<>(75);
        t.left.right.left = new BST<>(63);
        t.right.left = new BST<>(125);
        t.right.right = new BST<>(200);
        preOrderPrintPaths(t, new ArrayDeque<>(10));
    }

    static <T> void preOrderPrintPaths(BST<T> node, Deque<BST<T>> q) {
        if (node == null)
            return;
        if (node.left != null) {
            q.addLast(node);
            preOrderPrintPaths(node.left, q);
        }
        if (node.right != null) {
            q.addLast(node);
            preOrderPrintPaths(node.right, q);
        }
        if (node.left == null && node.right == null) {
            System.out.println(q.stream().map(n -> n.key.toString()).collect(Collectors.joining
                    ("->")) + "->" + node.key );
        }
        if (!q.isEmpty())
            q.removeLast();
    }
}