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

Answer 2

//我在这里使用递归，它也适用于不是 BST 的二叉树

不需要迭代器，只需使用 Java ArrayList

    class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;
    public TreeNode(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

        /*
                 30
             20      50
           15  25   40  60
                          70
                            80
        // This would print
        30 20 15 
        30 20 25 
        30 50 40 
        30 50 60 70 80 
        */

public class AllPathsToLeafArrayList {
    private static void findPaths(TreeNode root) {
        ArrayList list = new ArrayList();
        findPaths(root, list);
    }
    private static void findPaths(TreeNode root, List list) {
        if (root == null)
            return;
        list.add(root.data);
        if (root.left == null && root.right == null) {
            printPaths(list);
        } else {
            findPaths(root.left, list);
            findPaths(root.right, list);
        }
        list.remove(list.size() - 1);
    }
    private static void printPaths(List list) {
        for (Integer l : list) {
            System.out.print(l + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {

        TreeNode root = new TreeNode(30);
        root.left = new TreeNode(10);
        root.right = new TreeNode(50);
        root.left.left = new TreeNode(15);
        root.left.right = new TreeNode(25);
        root.right.left = new TreeNode(40);
        root.right.right = new TreeNode(60);
        root.right.right.right = new TreeNode(70);
        root.right.right.right.right = new TreeNode(80);
        findPaths(root);
    }
}

Answer 3

终于设法修复了我的代码。为了完整起见而发布。

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

    }

Answer 4

不确定为什么要为此目的使用队列。相反，您应该使用堆栈及其推送和弹出操作。然后代码非常简单。

    import com.algo2prepare.util.Tree;
    import java.util.Stack;
    public static void main(String[] args) {
        Node root = Tree.generate(Node.class, 4);
        Stack<Integer> stack = new Stack<>();
        Tree.print(root);
//                  71
//           ┌───────┴───────┐               
//          20              59
//       ┌───┴───┐       ┌───┴───┐       
//      64      89      67      89
//     ┌─┘     ┌─┴─┐           ┌─┘     
//    27      63  11          83    
        pathPrint(root, stack);
//  [71, 20, 64, 27]
//  [71, 20, 64, 89, 63]
//  [71, 20, 64, 89, 63, 11]
//  [71, 20, 64, 89, 59, 67]
//  [71, 20, 64, 89, 59, 67, 89, 83]
    
    }
    
    public static void pathPrint(Node node, Stack<Integer> stack) {
        if (node == null) { return; }
        stack.push(node.val);
        if (node.left == null && node.right == null) {
            System.out.println(stack);
            return;
        }
        pathPrint(node.left,stack);
        pathPrint(node.right,stack);
        stack.pop();
    }
    class Node {
        int val;
        Node left;
        Node right;
    }

请注意，只有二叉树很重要。二叉搜索树只是一个特例，但关键是这段代码也适用于 BST。