从深度优先搜索输出构造完美的二叉树

Question

假设你有一棵完美的二叉树，就像这样

         0
     /        \
    1           2      
   / \         / \
  3    4       5   6
 / \  / \    / \   / \
7  8 9  10 11  12 13 14 

给定其深度和作为深度优先搜索数组的节点值输出，例如。

深度：[4]

Dfs数组：[0,1,3,7,8,4,9,10,2,5,11,6,13,14]

编写将其作为二叉树返回的代码。你会怎么做（递归/非递归）？

我不确定是否有可能递归地解决这个问题，因为我不知道哪些节点是叶子而不是叶子。有了这些信息，人们就可以递归地构建树。在没有递归的情况下，我试图做一些类似的事情，但是我一直在做。

TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}

TreeNode makeTree(int[] dfs, int depth) {
    TreeNode root = new TreeNode(dfs[0]);
    Deque<TreeNode> dq = new LinkedList<>();
    dq.addFirst(root);

    while (!dq.isEmpty()) {
        int i;
        for (i = 1; i < depth - 1; i++) {
           TreeNode t = dq.getFirst();
           t.left = new TreeNode(dfs[i]);
           dq.addFirst(t.left);
    }
    TreeNode t = dq.getFirst();
    t.left = new TreeNode(dfs[i++]);
    dq.addFirst(t.left);
    t.right = new TreeNode(dfs[i++)];
    dq.addFirst(t.right);
   }
   // More code here to construct the tree?
   .........
   // return the root
   return dq.getLast();
}

Answer 1

以下代码从表示dfs结果的数组构建二叉树。
注意注释，如果它们还不够，请毫不犹豫地询问：

public class GraphFromDfs{

    public static void main(String[] args) {

        int[] dfsArray = new int[]{0,1,3,7,8,4,9,10,2,5,11,12,6,13,14};
        TreeNode root = makeTree(dfsArray, 4);
        printTreeFromRoot(root);
    }

    private static TreeNode makeTree(int[] dfsArray, int depth) {

        //array to store all nodes
        TreeNode[] nodes = new TreeNode[dfsArray.length];

        //create all nodes from int[] array
        for(int i=0; i< dfsArray.length; i++) {
            nodes[i]= new TreeNode(dfsArray[i]); //nodes stored in the same order as int array
        }

        makeTree(nodes, depth);
        return nodes[0] ;
    }

    //process nodes to add links (create a tree)
    private static void makeTree(TreeNode[] nodes, int depth) {

        int currentDepth = 0;
        int index = 0; //index of node in nodes array
        TreeNode root = nodes[0];
        //stack all nodes to be processed. add root as first
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);

        while (! stack.isEmpty()) {

            TreeNode node = stack.peekLast();

            if(node.left == null) { node.left = nodes[++index]; }         //process left or right if
            else if (node.right == null) { node.right = nodes[++index]; } //any is null. update index

            //add next node to stack to be processed if not a leaf.
            //leaf does not need to be processed
            if((currentDepth +2) < depth ) {

                stack.add(nodes[index]);
                currentDepth++;

            //if leaf - backtrack. move up the tree
            //note that this is in line with "perfect binary tree" as asked
            }else if((node.right != null) && (node.left != null)) {

                while (! stack.isEmpty()) {
                    TreeNode n = stack.peekLast();
                    if((n.left != null) && (n.right != null)) {
                        stack.remove(n); //remove fully processed nodes
                                         //(right and left are not null)
                        currentDepth --; //backtrack
                    }else {
                        break;
                    }
                }
            }
        }
    }

    private static void printTreeFromRoot(TreeNode root) {

        if(root == null) { return;}
        System.out.println("--------- TREE  ---------");
        System.out.println( root);
        printTree(root);
        System.out.println("--------------------------");
    }

    //recursive tree print
    private static void printTree(TreeNode root) {

        if(root.left != null ) {
            System.out.println( root.left);
            printTree(root.left);
        }
        if(root.right != null ) {
            System.out.println( root.right);
            printTree(root.right);
        }
    }
}

class TreeNode {

    int value;
    TreeNode left, right;

    TreeNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {

        StringBuilder s = new StringBuilder("N:"+ value);
        s.append( left == null ? " L-null" : " L-"+left.value);
        s.append( right == null ? " R-null" : " R-"+right.value);
        return s.toString();
    }
}

输出