二叉树相关

一、概念

二、题目

2.1 把数组转换成二叉树

2.2.1 使用队列方式

public static Node getTreeFromArr2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        LinkedList<Node> quque = new LinkedList<>();
        Node root = new Node(arr[0]);

        quque.add(root);
        int index = 1;
        while(!quque.isEmpty()){
            // pop 0的时候，刚好操作1、2
            // pop 1的时候，刚好操作3、4
            // pop 2的时候，刚好操作5、6
            Node temp = quque.pop();
            if(index < arr.length){
                temp.left = new Node(arr[index]);
                quque.add(temp.left);
                index++;
            }

            if(index < arr.length){
                temp.right = new Node(arr[index]);
                quque.add(temp.right);
                index++;
            }
        }
        return root;
    }

2.2.3 使用堆的方式

private static Node getTreeFromArr(int[] arr) {
        Map<Integer, Node> map = new HashMap();
        for (int i = arr.length - 1; i >= 0; i--) {
            Node temp = new Node(arr[i]);
            temp.value = arr[i];
            map.put(i, temp);
            int leftChildIndex = 2 * i + 1;
            int rightChildIndex = 2 * i + 2;
            if (leftChildIndex < arr.length) {
                temp.left = map.get(leftChildIndex);
            }
            if (rightChildIndex < arr.length) {
                temp.right = map.get(rightChildIndex);
            }
        }
        return map.get(0);
    }

2.2 二叉树进行前序、中序、后序遍历

2.2.1 递归的方式

@ToString
    public static class Node {
        public Node left;
        public Node right;
        public int value;

        public Node(int value) {
            this.value = value;

        }
    }

    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5, 6};
//        Node head = getTreeFromArr(arr);
        Node head2 = getTreeFromArr2(arr);
//        System.out.println(JSON.toJSONString(head));
        System.out.println(JSON.toJSONString(head2));

        /*
            前序遍历：[0, 1, 3, 4, 2, 5, 6]
            中序遍历：[3, 1, 4, 0, 5, 2, 6]
            后序遍历：[3, 4, 1, 5, 6, 2, 0]
         */
        preorderPrint(head2);
        System.out.println();
        inorderPrint(head2);
        System.out.println();
        postorderPrint(head2);
    }

    /**
     * 前序遍历（中左右）
     */
    public static void preorderPrint(Node temp){
        if(null == temp){
            return;
        }
        System.out.print(temp.value + ",");
        preorderPrint(temp.left);
        preorderPrint(temp.right);
    }

    /**
     * 中序遍历（左中右）
     */
    public static void inorderPrint(Node temp){
        if(null == temp){
            return;
        }
        inorderPrint(temp.left);
        System.out.print(temp.value + ",");
        inorderPrint(temp.right);
    }
    /**
     * 右序遍历（左中右）
     */
    public static void postorderPrint(Node temp){
        if(null == temp){
            return;
        }
        postorderPrint(temp.left);
        postorderPrint(temp.right);
        System.out.print(temp.value + ",");
    }


    public static Node getTreeFromArr2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        LinkedList<Node> quque = new LinkedList<>();
        Node root = new Node(arr[0]);

        quque.add(root);
        int index = 1;
        while(!quque.isEmpty()){
            // pop 0的时候，刚好操作1、2
            // pop 1的时候，刚好操作3、4
            // pop 2的时候，刚好操作5、6
            Node temp = quque.pop();
            if(index < arr.length){
                temp.left = new Node(arr[index]);
                quque.add(temp.left);
                index++;
            }

            if(index < arr.length){
                temp.right = new Node(arr[index]);
                quque.add(temp.right);
                index++;
            }
        }
        return root;
    }

2.2.2 栈的方式

1、前序遍历（宽度遍历）

/**
     * Stack方法
     * 前序遍历（中左右）
     */
    public static void preorderPrintByStack(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        // 可以不用queue，可以直接打印，省空间 N
        // 我加一个 queue的目的是为了后序的翻转好理解
        Queue<Node> queue = new LinkedList<>();

        while (!stack.isEmpty()) {
            Node temp = stack.pop();
//            System.out.print(temp.value + ",");
            // 此处可以不打印，直接入一个新的 queue
            queue.offer(temp);
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
        }
        System.out.print("preorderPrintByStack -> ");
        while (!queue.isEmpty()) {
            System.out.print(queue.poll().value + ",");
        }
        System.out.println();
    }

/**
     * 宽度遍历，其实就是中左右，也就是前序遍历
     * 用一个 queue 辅助也是可以搞定的
     * @param head
     */
    public static void widthPrint(Node head){
        if(null == head){
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(head);

        while(!queue.isEmpty()){
            Node temp = queue.poll();
            System.out.print(temp.value + ",");
            if(temp.left != null){
                queue.offer(temp.left);
            }
            if(temp.right != null){
                queue.offer(temp.right);
            }
        }
    }

2、中序遍历


    /**
     * Stack方法
     * 中序遍历（左中右）
     */
    public static void inOrderPrintByStack(Node root) {
        if(null == root){
            return;
        }
        Node current = root;
        Stack<Node> stack = new Stack<>();

        // 可以不用queue，可以直接打印，省空间 N
        // 我加一个 queue的目的是为了后序的翻转好理解
        Queue<Node> queue = new LinkedList<>();

        while (current != null || !stack.isEmpty()) {
            // 如果current不是null，那么就一直往左找下去
            while(current != null){
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
//            System.out.print(current.value + ",");
            queue.offer(current);
            // 左边已经干完了，那么就一直往右找
            current = current.right;
        }

        System.out.print("inOrderPrintByStack -> ");
        while (!queue.isEmpty()) {
            System.out.print(queue.poll().value + ",");
        }
    }

3、右序遍历

/**
     * 右序遍历（左右中）
     * 翻过来就是 中右左， 因为前序是中左右，前序是先压right再压left，那么反过来，先压left再压right的话，就会是中右左了
     */
    public static void postorderPrintByStack(Node temp) {
        if (null == temp) {
            return;
        }
        Stack<Node> stackA = new Stack<>();
        stackA.push(temp);

        // 注意和之前的区别，上面的中序和前序都是 queue ，FIFO，那么 Stack 的FILO，就能实现这个翻转
        Stack<Node> stackB = new Stack<>();

        while(!stackA.isEmpty()){
            temp = stackA.pop();
            stackB.push(temp);
            if(temp.left != null){
                stackA.push(temp.left);
            }
            if(temp.right != null){
                stackA.push(temp.right);
            }
        }

        System.out.print("postorderPrintByStack -> ");
        while (!stackB.isEmpty()) {
            System.out.print(stackB.pop().value + ",");
        }
    }

0、测试代码汇总

@ToString
    public static class Node {
        public Node left;
        public Node right;
        public int value;

        public Node(int value) {
            this.value = value;

        }
    }

    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5, 6};
//        Node head = getTreeFromArr(arr);
        Node head2 = getTreeFromArr2(arr);
//        System.out.println(JSON.toJSONString(head));
        System.out.println(JSON.toJSONString(head2));

        /*
            前序遍历：[0, 1, 3, 4, 2, 5, 6]
            中序遍历：[3, 1, 4, 0, 5, 2, 6]
            后序遍历：[3, 4, 1, 5, 6, 2, 0]
         */

        System.out.println("preorderPrint ->");
        preorderPrint(head2);
        System.out.println();

        System.out.println("inorderPrint ->");
        inorderPrint(head2);
        System.out.println();

        System.out.println("postorderPrint ->");
        postorderPrint(head2);
        System.out.println();
        System.out.println("——————————");


        preorderPrintByStack(head2);
        inOrderPrintByStack(head2);
        postorderPrintByStack(head2);
    }

    /**
     * 前序遍历（中左右）
     */
    public static void preorderPrint(Node temp) {
        if (null == temp) {
            return;
        }
        System.out.print(temp.value + ",");
        preorderPrint(temp.left);
        preorderPrint(temp.right);
    }

    /**
     * 中序遍历（左中右）
     */
    public static void inorderPrint(Node temp) {
        if (null == temp) {
            return;
        }
        inorderPrint(temp.left);
        System.out.print(temp.value + ",");
        inorderPrint(temp.right);
    }

    /**
     * 右序遍历（左中右）
     */
    public static void postorderPrint(Node temp) {
        if (null == temp) {
            return;
        }
        postorderPrint(temp.left);
        postorderPrint(temp.right);
        System.out.print(temp.value + ",");
    }

    /**
     * Stack方法
     * 前序遍历（中左右）
     */
    public static void preorderPrintByStack(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        // 可以不用queue，可以直接打印，省空间 N
        // 我加一个 queue的目的是为了后序的翻转好理解
        Queue<Node> queue = new LinkedList<>();

        while (!stack.isEmpty()) {
            Node temp = stack.pop();
//            System.out.print(temp.value + ",");
            // 此处可以不打印，直接入一个新的 queue
            queue.offer(temp);
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
        }
        System.out.print("preorderPrintByStack -> ");
        while (!queue.isEmpty()) {
            System.out.print(queue.poll().value + ",");
        }
        System.out.println();
    }

    /**
     * Stack方法
     * 中序遍历（左中右）
     */
    public static void inOrderPrintByStack(Node root) {
        if(null == root){
            return;
        }
        Node current = root;
        Stack<Node> stack = new Stack<>();

        // 可以不用queue，可以直接打印，省空间 N
        // 我加一个 queue的目的是为了后序的翻转好理解
        Queue<Node> queue = new LinkedList<>();

        while (current != null || !stack.isEmpty()) {
            // 如果current不是null，那么就一直往左找下去
            while(current != null){
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
//            System.out.print(current.value + ",");
            queue.offer(current);
            // 左边已经干完了，那么就一直往右找
            current = current.right;
        }

        System.out.print("inOrderPrintByStack -> ");
        while (!queue.isEmpty()) {
            System.out.print(queue.poll().value + ",");
        }
    }


    /**
     * 右序遍历（左右中）
     * 翻过来就是 中右左， 因为前序是中左右，前序是先压right再压left，那么反过来，先压left再压right的话，就会是中右左了
     */
    public static void postorderPrintByStack(Node temp) {
        if (null == temp) {
            return;
        }
        Stack<Node> stackA = new Stack<>();
        stackA.push(temp);

        // 注意和之前的区别，上面的中序和前序都是 queue ，FIFO，那么 Stack 的FILO，就能实现这个翻转
        Stack<Node> stackB = new Stack<>();

        while(!stackA.isEmpty()){
            temp = stackA.pop();
            stackB.push(temp);
            if(temp.left != null){
                stackA.push(temp.left);
            }
            if(temp.right != null){
                stackA.push(temp.right);
            }
        }

        System.out.print("postorderPrintByStack -> ");
        while (!stackB.isEmpty()) {
            System.out.print(stackB.pop().value + ",");
        }
    }




    public static Node getTreeFromArr2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        LinkedList<Node> quque = new LinkedList<>();
        Node root = new Node(arr[0]);

        quque.add(root);
        int index = 1;
        while (!quque.isEmpty()) {
            // pop 0的时候，刚好操作1、2
            // pop 1的时候，刚好操作3、4
            // pop 2的时候，刚好操作5、6
            Node temp = quque.pop();
            if (index < arr.length) {
                temp.left = new Node(arr[index]);
                quque.add(temp.left);
                index++;
            }

            if (index < arr.length) {
                temp.right = new Node(arr[index]);
                quque.add(temp.right);
                index++;
            }
        }
        return root;
    }