二叉树入门

二叉树的存储方式，如何根据存储方式还原二叉树，热门题目

1. 存前序和中序
2. 存后续和中序

还原二叉树

根据前序中序还原二叉树

找特点

区别 :

• 前序的根节点在 第一位，中序的根节点在中间
• 只要找到左子树的数量，右子树也可以随之实现

    public static TreeNode buildTree(int[] qian, int[] zhong) {
        if (qian == null || zhong == null || qian.length == 0 || zhong.length == 0 || qian.length != zhong.length) {
            return null;
        }
        //   从前序遍历中找到根节点
        TreeNode root = new TreeNode(qian[0]);
        int rootindex = 0;
        int rootval = root.val;
        //从中序数组中找到 root
        for (int i = 0; i < zhong.length; i++) {
            if (zhong[i] == rootval) {
                rootindex = i;
            }
        }
        //找到左子树的前序和中序
        int[] leftZhong = Arrays.copyOfRange(zhong, 0, rootindex);
        int[] leftQian = Arrays.copyOfRange(qian, 1, rootindex + 1);
        //找到右子树的前序和中序
        int[] rightZhong = Arrays.copyOfRange(zhong, rootindex + 1, zhong.length);
        int[] rightQian = Arrays.copyOfRange(qian, rootindex + 1, qian.length);
        //    递归构建左右子树
        TreeNode left = buildTree(leftQian, leftZhong);
        TreeNode right = buildTree(rightQian, rightZhong);
        //    给根节点添加左右子树
        root.left = left;
        root.right = right;
        return root;
    }

效率版

TreeNode build(int[] preorder, int preStart, int preEnd, 
               int[] inorder, int inStart, int inEnd) {
    // root 节点对应的值就是前序遍历数组的第一个元素
    int rootVal = preorder[preStart];
    // rootVal 在中序遍历数组中的索引
    int index = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == rootVal) {
            index = i;
            break;
        }
    }

    TreeNode root = new TreeNode(rootVal);
    // 递归构造左右子树
    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, index - 1);

    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, index + 1, inEnd);
    return root;
}

根据中序后序还原二叉树

找特点

区别 :

• 后序的根节点在 最后位，中序的根节点在中间
• 只要找到左子树的数量，右子树也可以随之实现

    public static TreeNode buildTree(int[] zhong, int[] hou) {
        if (hou == null || zhong == null || hou.length == 0 || zhong.length == 0 || hou.length != zhong.length) {
            return null;
        }
        //   从后序遍历中找到根节点
        TreeNode root = new TreeNode(hou[hou.length - 1]);
        int rootindex = 0;
        int rootval = root.val;
        //从中序数组中找到 root
        for (int i = 0; i < zhong.length; i++) {
            if (zhong[i] == rootval) {
                rootindex = i;
            }
        }
        //找到左子树的中序和后序
        int[] leftZhong = Arrays.copyOfRange(zhong, 0, rootindex);
        int[] leftHou = Arrays.copyOfRange(hou, 0, rootindex);
        //找到右子树的中序和后序
        int[] rightZhong = Arrays.copyOfRange(zhong, rootindex + 1, zhong.length);
        int[] rightHou = Arrays.copyOfRange(hou, rootindex, hou.length - 1);
        //    递归构建左右子树
        TreeNode left = buildTree(leftZhong, leftHou);
        TreeNode right = buildTree(rightZhong, rightHou);
        //    给根节点添加左右子树
        root.left = left;
        root.right = right;
        return root;
    }

效率版

// 存储 inorder 中值到索引的映射
HashMap<Integer, Integer> valToIndex = new HashMap<>();

TreeNode buildTree(int[] inorder, int[] postorder) {
    for (int i = 0; i < inorder.length; i++) {
        valToIndex.put(inorder[i], i);
    }
    return build(inorder, 0, inorder.length - 1,
                 postorder, 0, postorder.length - 1);
}

/* 
    build 函数的定义：
    后序遍历数组为 postorder[postStart..postEnd]，
    中序遍历数组为 inorder[inStart..inEnd]，
    构造二叉树，返回该二叉树的根节点 
*/
TreeNode build(int[] inorder, int inStart, int inEnd,
               int[] postorder, int postStart, int postEnd) {
    // root 节点对应的值就是后序遍历数组的最后一个元素
    int rootVal = postorder[postEnd];
    // rootVal 在中序遍历数组中的索引
    int index = valToIndex.get(rootVal);

    TreeNode root = new TreeNode(rootVal);
    // 递归构造左右子树
    root.left = build(preorder, ?, ?,
                      inorder, ?, ?);

    root.right = build(preorder, ?, ?,
                       inorder, ?, ?);
    return root;
}

树的搜索

深度优先

就是有限向下来搜索，

二叉树深度优先的代码也非常的好理解

    public static boolean dfs(TreeNode root, int target) {
        if (root == null) {
            return false;
        }
        if (root.val == target) {
            return true;
        }
        return dfs(root.left, target) || dfs(root.right, target);
    }

广度优先

按照一层一层的找吗，有限寻找同一层的

代码

判断是否存在的

    public static boolean bfs(ArrayList<TreeNode> roots, int target) {
        System.out.println(roots.get(0).val);
        if (roots == null || roots.size() == 0) {
            return false;
        }
        ArrayList<TreeNode> childRoots = new ArrayList<>();
        for (TreeNode temp : roots) {
            if (temp.val == target) {
                return true;
            }
            if (temp.left != null) {
                childRoots.add(temp.left);
            }
            if (temp.right != null) {
                childRoots.add(temp.right);
            }
        }
        return bfs(childRoots, target);
    }

    public static boolean bfs(TreeNode root, int target) {
        ArrayList<TreeNode> roots = new ArrayList<>();
        roots.add(root);
        return bfs(roots, target);
    }

第二种解法

返回输出集合的

    public static List<Integer> bfs(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> list = new LinkedList<Integer>();

        if (root == null) {
            return list;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode t = queue.remove();
            if (t.left != null) {
                queue.add(t.left);
            }
            if (t.right != null) {
                queue.add(t.right);
            }
            list.add(t.val);
        }
        return list;
    }

树的比较

完全相等 才算通过

很简单的递归思路，

    public static boolean compareTree(TreeNode tree1, TreeNode tree2) {
        if (tree1 == null && tree2 != null || tree1 != null && tree2 == null) {
            return true;
        }
        if (tree1 == null || tree2 == null) {
            return true;
        }
        if (tree1.val != tree2.val) {
            return false;
        }
        return compareTree(tree1.left, tree2.left) && compareTree(tree1.right, tree2.right);
    }

左右子树互换也算相等

需要修改一些条件，只需要在返回结果加上一个或者条件，tree1和tree2的左右子树分别比较即可

    public static boolean compareTree(TreeNode tree1, TreeNode tree2) {
        if (tree1 == null && tree2 != null || tree1 != null && tree2 == null) {
            return true;
        }
        if (tree1 == null || tree2 == null) {
            return true;
        }
        if (tree1.val != tree2.val) {
            return false;
        }
        return compareTree(tree1.left, tree2.left) && compareTree(tree1.right, tree2.right)
                || compareTree(tree1.left, tree2.right) && compareTree(tree1.right, tree2.left);
    }