java - 在 Java 中从 preOrder 数组实现二叉搜索树重建？

Question

我关注了this idea还有这个C++ code在 Java 中从 PreOrder 数组重建二叉搜索树。我不是重新发明算法，而是尝试实现伪代码。我在这里需要帮助。我没有得到正确的输出。我得到的输出在代码下方。

public class BinaryTreeMethods {           
        public static void main(String[] args) {

        int[] arr = {7,5,3,6,9,8,10};
        Node newone = CreateFromPreOrder(arr,arr.length);
            printInorder(newone);
            System.out.println();
            printPreOrder(newone);

public static Node CreateFromPreOrder(int[] arr, int length) {

            if(length==0)
               return null;
            Node root = new Node(arr[0]);
            Stack<Node> s = new Stack<Node>();
            s.push(root);
            for(int i=1; i<length; i++)
            {

            Node tmp = new Node(arr[i]);
            Node next = s.peek();
            if(tmp.data < next.data)
            {
            next.left = tmp;
            }
            else
            {
            Node popped = null;
            while(!s.isEmpty() && tmp.data > next.data)
            {
            popped= s.peek();
            s.pop();
            }
            popped.right = tmp;
            }
            s.push(tmp);
            }
            return root;
            }
     public static void printInorder(Node root) {

            if (root!=null){
                printInorder(root.left);
                System.out.print(" " + root.data);
                printInorder(root.right);
            }
        }

class Node {
    Node left;
    Node right;
    int data;

    public Node(int c){
        this(c, null, null);
    }
    public Node(int c,Node left, Node right) {
        this.data = c;
        this.left=left;
        this.right=right;
    }


}




     public static void printInorder(Node root) {

            if (root!=null){
                printInorder(root.left);
                System.out.print(" " + root.data);
                printInorder(root.right);
            }
        }


public static void printPreOrder(Node root) {

            if (root!=null){
                System.out.print(" " + root.data);
                printInorder(root.left);
                printInorder(root.right);
            }
        }
            } 

我没有得到预期的输出:

3 5 7 6 8 9 10
 7 3 5 6 8 9 10

Answer 1

看起来递归打印搞砸了。这里printPreOrder应该调用自己遍历左右子树，而不是调用printInOrder来遍历。

public static void printPreOrder(Node root) {

            if (root!=null){
                System.out.print(" " + root.data);
                printPreOrder(root.left); 
                printPreOrder(root.right);
            }
        }
    }