二叉树入门
二叉树的存储方式，如何根据存储方式还原二叉树，热门题目
- 存前序和中序
- 存后续和中序
还原二叉树
根据前序中序还原二叉树
找特点
区别 :
- 前序的根节点在 第一位，中序的根节点在中间
- 只要找到左子树的数量，右子树也可以随之实现
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); }
