yaohustiAC 2020-01-03
LeetCode收录了许多互联网公司的算法题目,被称为刷题神器。最近在剑指Offer上也刷了一些题目,发现涉及到数据结构类的题目,比如说“树”、“链表"这种题目,如果想在本地IDE进行测试,除了完成题目要求的算法外,还需要写一些辅助函数,比如树的创建,遍历等,由于这些函数平时用到的地方比较多,并且也能加深对常用数据结构的理解,这里将Leetcode中与树(TreeNode)相关题目会用到的测试辅助函数做一个总结。
1.TreeNode.java
package structure; public class TreeNode { public int val = 0; public TreeNode left = null; public TreeNode right = null; public TreeNode(int val) { this.val = val; } }
2.TreeHelper.java
package structure; import static java.lang.Math.max; public class TreeHelper { static int index; static String[] values; public TreeHelper(){} // 根据形如”1,2,#,4,5,#,7,#“的字符串建立二叉树,其中#代表该节点为空 public void setValues(String treeValues) { values = treeValues.split(","); index = 0; } // 递归建立二叉树 public TreeNode createTree() { TreeNode node = null; if(index < values.length){ if (values[index].equals("#")) { index++; return null; } node = new TreeNode(Integer.parseInt(values[index])); index++; node.left = createTree(); node.right = createTree(); } return node; } //前序遍历 public void preOrder(TreeNode root) { if (root == null) { return; } else { System.out.print(root.val + " "); preOrder(root.left); preOrder(root.right); } } //中序遍历 public void inOrder(TreeNode root) { if (root == null) { return; } else { preOrder(root.left); System.out.print(root.val + " "); preOrder(root.right); } } //后序遍历 public void postOrder(TreeNode root) { if (root == null) { return; } else { preOrder(root.left); preOrder(root.right); System.out.print(root.val + " "); } } //获取二叉树的节点个数 public int getNodeNum(TreeNode root) { if (root == null) { return 0; } return 1 + getNodeNum(root.left) + getNodeNum(root.right); } //获取二叉树的高度 public int getTreeHeight(TreeNode root) { if (root == null) { return 0; } return 1 + max(getTreeHeight(root.left), getTreeHeight(root.right)); } //创建二叉搜索树BST public TreeNode createSearchTree(int[] treeValues){ TreeNode rootBST = null; for (int value : treeValues) { rootBST = insertNode(rootBST,value); } return rootBST; } //判断一个二叉树是否为二叉搜索树,时间复杂度O(1) public boolean isBST(TreeNode root) { return isBSTResolve(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } public boolean isBSTResolve(TreeNode root, int min, int max) { if (root == null) { return true; } if (root.val < min || root.val > max) { return false; } return isBSTResolve(root.left, min, root.val) && isBSTResolve(root.right, root.val, max); } //根据值查找二叉树搜索树root的某个节点 public TreeNode findNode(TreeNode rootBST, int val) { if (rootBST == null) { return null; } else if (rootBST.val < val) { return findNode(rootBST.right, val); } else if (rootBST.val > val) { return findNode(rootBST.left, val); } return rootBST; } //向二叉搜索树中插入值val public TreeNode insertNode(TreeNode rootBST, int val) { if (rootBST == null) { rootBST = new TreeNode(val); } else { if (val < rootBST.val) { rootBST.left = insertNode(rootBST.left, val); } else if (val > rootBST.val) { rootBST.right = insertNode(rootBST.right, val); } } return rootBST; } //删除二叉树中某个值为val的节点 public TreeNode deleteNode(TreeNode rootBST, int val) { if (findNode(rootBST, val) == null) { System.out.println("要删除的节点不存在!"); } else { if (val < rootBST.val) { rootBST.left = deleteNode(rootBST.left, val); } else if (val > rootBST.val) { rootBST.right = deleteNode(rootBST.right, val); } else { //rootBST就是要被删除的节点 if (rootBST.left != null && rootBST.right != null) { //被删除的节点的左右子节点均存在 TreeNode tmp = findMinNode(rootBST.right); //从右子树找到值最小的节点填充删除节点 rootBST.val = tmp.val; rootBST.right = deleteNode(rootBST.right, rootBST.val); //删除右子树值最小的元素 } else { //被删除的节点只有一个或者无子节点存在 //被删除节点的左子节点为空,则右子节点取代根节点 if (rootBST.left == null) { rootBST = rootBST.right; } else { rootBST = rootBST.left; } } } } return rootBST; } // 找到二叉搜索树中值最小的节点 public TreeNode findMinNode(TreeNode rootBST) { if (rootBST == null) { return null; } else if (rootBST.left == null) { return rootBST; } return findMinNode(rootBST.left); } }
3.TreeHelperTest.java
package test; import structure.TreeHelper; import structure.TreeNode; class treeHelperTest { public static void main(String[] args) { String treeNodeValues = "1,2,#,#,3,4,#,#,5,6,#,8,#,#"; TreeHelper treeHelper = new TreeHelper(); treeHelper.setValues(treeNodeValues); try { TreeNode root = treeHelper.createTree(); System.out.println("创建二叉树成功!"); System.out.println("前序遍历二叉树:"); treeHelper.preOrder(root); System.out.println(); System.out.println("中序遍历二叉树:"); treeHelper.inOrder(root); System.out.println(); System.out.println("后序遍历二叉树:"); treeHelper.postOrder(root); System.out.println(); System.out.printf("二叉树的节点数目:%d\n", treeHelper.getNodeNum(root)); System.out.printf("二叉树的高度:%d\n", treeHelper.getTreeHeight(root)); System.out.println("二叉树是否为二叉搜索树:" + String.valueOf(treeHelper.isBST(root))); } catch (Exception e) { e.printStackTrace(); } try { TreeNode rootBST = treeHelper.createSearchTree(new int[]{2, 4, 3, 1, 9, 7, 6, 8}); System.out.println("创建二叉搜索树成功!"); System.out.println("二叉树是否为二叉搜索树:" + String.valueOf(treeHelper.isBST(rootBST))); System.out.println("中序遍历二叉搜索树:"); treeHelper.inOrder(rootBST); System.out.println(); rootBST = treeHelper.insertNode(rootBST, 5); System.out.println("中序遍历插入5后的二叉搜索树:"); treeHelper.inOrder(rootBST); System.out.println(); rootBST = treeHelper.deleteNode(rootBST, 6); System.out.println("中序遍历删除6后的二叉搜索树:"); treeHelper.inOrder(rootBST); System.out.println(); } catch (Exception e) { e.printStackTrace(); } } }
测试结果如下
4.剑指Offer在线编程第18道题"二叉树的镜像"
Solution18
import structure.TreeHelper; import structure.TreeNode; /* * Q:操作给定的二叉树,将其变换为源二叉树的镜像 * tag: 树 */ public class Solution18 { public static void main(String[] args) { Solution18 s = new Solution18(); s.testMirror(); } public void Mirror(TreeNode root) { if(root == null){ return; } if(root.left == null){ root.left = root.right; root.right = null; Mirror(root.left); } else if(root.right == null){ root.right = root.left; root.left = null; Mirror(root.right); } else{ TreeNode temp = root.left; root.left = root.right; root.right = temp; Mirror(root.right); Mirror(root.left); } } public void testMirror(){ TreeHelper treeHelper = new TreeHelper(); String treeValues = "1,2,#,#,3,4,#,#,5,6,#,8,#,#"; treeHelper.setValues(treeValues); TreeNode root = treeHelper.createTree(); System.out.println("中序遍历二叉树:"); treeHelper.inOrder(root); System.out.println(); Mirror(root); System.out.println("中序遍历二叉树的镜像:"); treeHelper.inOrder(root); System.out.println(); } }
运行结果如下: