剑指offerDayN树篇 – 源码巴士

根据前序中序递归重建二叉树

package offer;

import java.util.Arrays;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

/*
前序中序重建二叉树
Arrays.copyOfRange()
主要用于对一个已有的数组进行截取复制，复制出一个左闭右开区间的数组。
 */
public class Test31 {
    //递归调用构建树
    public static TreeNode reConstruct(int[] preOrder, int[] inOrder) {
        //先判空
        if (preOrder.length == 0 || preOrder == null) return null;
        //构建二叉树
        TreeNode root = new TreeNode(preOrder[0]);
        //查找根节点在中序之间的位置下标 每次左子树 跟右子树范围会发生变化
        int index = findIndex(preOrder, inOrder);
        //递归左子树
        //中序index其实就是他的长度
        root.left = reConstruct(Arrays.copyOfRange(preOrder, 1, index + 1), Arrays.copyOfRange(inOrder, 0, index));
        //递归右子树
        root.right = reConstruct(Arrays.copyOfRange(preOrder, index + 1, preOrder.length), Arrays.copyOfRange(inOrder, index + 1, inOrder.length));

        return root;
    }

    /**
     * 根据前序中序查找每次的根节点对应的下标
     *
     * @param preOrder
     * @param inOrder
     * @return
     */
    public static int findIndex(int[] preOrder, int[] inOrder) {
        //每次的根节点都是在变化的
        int root = preOrder[0];
        for (int i = 0; i < preOrder.length; i++) {
            if (inOrder[i] == root)
                return i;
        }
        return -1;
    }

    //二叉树前序遍历 非递归

    /**
     * 用栈实现非递归
     *
     * @param root
     */
    public static void preOrder(TreeNode root) {
        //先判空
        if (root == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val+" ");
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);

        }
    }

    public static void main(String[] args) {
        int[] preOrder = new int[]{1, 2, 4, 7, 3, 5, 6, 8};
        int[] inOrder = new int[]{4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode tree = reConstruct(preOrder, inOrder);
        preOrder(tree);
    }
}

层序遍历+按照节点位置输出层序遍历

树递归专栏：1树的镜像 2树的高度 3是否为平衡二叉树

package offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
1从上到下层序遍历树
2按照节点个数遍历树
3 二叉树镜像 对二叉树进轴对称
    先对左右子树镜像
    再对子树里面的数值进行求镜像
4求树的深度---递归经典套路
5判断树是不是平衡二叉树
 */
public class Test32 {
    public static void bfsOrder(TreeNode root) {
        //判空
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
    }

    /**
     * 按照每行有多少节点返回
     *
     * @param root
     */
    public static List<List<Integer>> bfsOrder2(TreeNode root) {
        //判空
        if (root == null) return null;
        List<List<Integer>> lists = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            //每次新建一个列表
            List<Integer> temp = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            lists.add(temp);
        }
        return lists;
    }

    /**
     * 递归
     * 先对左右子树镜像
     * 再对子树里面的数值进行求镜像
     *
     * @param root
     * @return
     */
    public static TreeNode mirrorTree(TreeNode root) {
        if (root == null) return null;
        //递归翻转子节点
        //定义零时变量 右边放到左边 然后再把左边放到右边
        TreeNode temp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        return root;

        /*
        写的复杂点
        获得翻转子树
        TreeNode l = mirrorTree(root.left);
        TreeNode r = mirrorTree(root.right);
        子树互换
        root.left = l;
        root.right = r;
        return root;
         */
    }

    /**
     * 递归求二叉树的高度
     * 返回左右子树的高度加1
     *
     * @param root
     * @return
     */
    public static int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        return l > r ? l + 1 : r + 1;
    }

    //平衡二叉树 任意节点的左右子树的高度不相差1 就是平衡二叉树

    /**
     * r任意节点
     * 高度相差1
     *
     * @param root
     * @return
     */
    public static boolean isBinarayTree(TreeNode root) {
        if (root == null) return true;
        //先求根节点左右两边子树的的深度差
        int l = maxDepth(root.left);
        int r = maxDepth(root.right);
        //|l-1|<=1
        //并且递归左右子树差都不能大于1
        return l - r >= -1 && l - r <= 1 && isBinarayTree(root.left) && isBinarayTree(root.right);
    }

    public static void main(String[] args) {
//构建一颗树
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, node6, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        bfsOrder(node1);
        System.out.println(bfsOrder2(node1));
        System.out.println();
        mirrorTree(node1);
        System.out.println(bfsOrder2(node1));
        System.out.println(maxDepth(node1));
        System.out.println(isBinarayTree(node1));
    }
}

三种层序遍历的方式

package offer;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
二叉树的打印
从上到下打印二叉树
1从上到下层序遍历
2分层打印
3之子形打印   特点 用linkedlist  头部插入比arraylist快很多
 */
public class Test33 {
    //基础的层序遍历bfs
    public static void bfsOrders(TreeNode root) {
        //判空
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
    }

    //按照每层的节点内容输出
    public static List<List<Integer>> bfsOrders2(TreeNode root) {
        //判空
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> list = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new LinkedList<>();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            list.add(temp);
        }
        return list;
    }

    //z形输出树的节点
    //奇数在队列后面添加 偶数在队里前面添加

    /**
     * 队列前面添加 queue.add(0,node.val)
     *添加flag指标 判断
     * @param root
     */
    public static List<List<Integer>> bfsOrders3(TreeNode root) {
        //判空
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> list = new LinkedList<>();
        queue.add(root);
        //每次输出一层
        //设置标识flag flag为true则添加
        boolean flag = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new LinkedList<>();
            while (size-->0){
                TreeNode node = queue.poll();
                if (flag) temp.add(node.val);// 从左往右
                else temp.add(0, node.val);//奇数从右往左
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            flag = !flag;
            list.add(temp);
        }
        return list;
    }

    public static void main(String[] args) {
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, node6, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        bfsOrders(node1);
        System.out.println();
        System.out.println(bfsOrders2(node1));
        System.out.println(bfsOrders3(node1));
    }
}

原文链接：https://blog.csdn.net/carpdiem_fan/article/details/125421523