public class BinaryDemo02 {

    public static void main(String[] args) {

        int preOrderArray[] = {1, 2, 4, 3, 6, 7};

        int infixOrderArray[] = {4, 2, 1, 6, 3, 7};

        BinaryTree b = new BinaryTree();

        HeroNode heroNode = new BinaryDemo02().buildTree(preOrderArray, infixOrderArray);

        b.setRoot(heroNode);

        LinkedList<HeroNode> s = new LinkedList<>();

        HeroNode root = heroNode;

        while(root != null || ! s.isEmpty()) {

            if(root != null) {

                s.push(root);

                System.out.println("前序遍历：" + root);

                root = root.getLeft();

            }else {

                HeroNode pop = s.pop();

                root = pop.getRight();

            }

        }

    }

    public HeroNode buildTree(int preOrder[], int inOrder[]) {

        if(preOrder.length == 0 || inOrder.length == 0) return null;

        // 通过前序遍历我们获取 root 节点 的值

        int rootValue = preOrder[0];

        // 将 root 节点 赋值给 节点类

        HeroNode root = new HeroNode(rootValue);

        for (int i = 0; i < inOrder.length; i++) {

            // 循环 如果 当前索引值等于 root 节点说明找到了 root 节点的索引位置了

            if (inOrder[i] == rootValue) {

                // 从 0 到 i - 1 就是左子树

                //copyOfRange 根据 区间 复制 一个数组 参数：inOrder 要复制的数组 区间：从 0 到 i-1 (含头不含尾 所以 i 就是 i - 1 的效果)

                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);// [4. 2]

                // 从 i + 1 到 inOrder.length - 1 就是右子树

                int[] inRight = Arrays.copyOfRange(inOrder, i + 1, inOrder.length);// [6, 3, 7]

                // 从 1 到 i - 1 就是左子树 因为需要 略过 0 索引的值 因为它就是 根节点 而我们要找的是 4，2 中谁是根 这时我们需要前序遍历的结果来判断

                int[] preLeft = Arrays.copyOfRange(preOrder, 1, i + 1);// [2, 4]

                // 从 i + 1 到 preOrder.length - 1 就是右子树

                int[] preRight = Arrays.copyOfRange(preOrder, i + 1, preOrder.length);// [3, 6, 7]

                root.setLeft(buildTree(preLeft, inLeft));// 2

                root.setRight(buildTree(preRight, inRight));// 3

                break;

            }

        }

        return root;

    }

}