06、数据结构与算法---二叉树

递归的精髓其实在于关注好当前结点尽可能少试图每次都将递归的过程在脑海里模拟一遍一、树的理解二叉树是最基本的树结构先从此学起这个结构像是生活中树的结构倒过来根结点在上叶子结点在最下二、手动实现这里实现了一些树性质上的操作相对简单public class MyTree { //结点类 static class TreeNode { public TreeNode left; public TreeNode right; public String val; public TreeNode() { } public TreeNode(String val) { this.val val; } } //前序遍历 private void preOrder(TreeNode root){ if(root null){ return; } System.out.print(root.val ); preOrder(root.left); preOrder(root.right); } //中序遍历 private void inOrder(TreeNode root){ if(root null){ return; } inOrder(root.left); System.out.print(root.val ); inOrder(root.right); } //后序遍历 private void postOrder(TreeNode root){ if(root null){ return; } postOrder(root.left); postOrder(root.right); System.out.print(root.val ); } //计算总结点个数 public int count 0; //一、计数器写法 public void size(TreeNode root) { if(root null){ return; } count; size(root.left); size(root.right); } //二、节点数 左子树 右子树 根节点 public int size2(TreeNode root) { if(root null){ return 0; } return size2(root.left) size2(root.right) 1; } //计算叶子结点个数 public int count2; //一、计数器写法 public void getLeafNodeCount(TreeNode root){ if (root null){ return; } if(root.left null root.right null){ count2; } getLeafNodeCount(root.left); getLeafNodeCount(root.right); } //二、叶子结点 左子树叶子 右子树叶子 public int getLeafNodeCount2(TreeNode root){ if (root null){ return 0; } if(root.left null root.right null){ return 1; } return getLeafNodeCount2(root.left) getLeafNodeCount2(root.right); } //求某一层的结点个数 //整棵树的第k层 左子树第k-1层 右子树第k-1层 public int getLevelNodeCount(TreeNode root,int k){ if(root null){ return 0; } if (k 1){ return 1; } return getLevelNodeCount(root.left,k-1) getLevelNodeCount(root.right,k-1); } //二叉树的高度 public int getMaxHeight(TreeNode root){ if (root null){ return 0; } int leftHeight getMaxHeight(root.left); int rightHeight getMaxHeight(root.right); return Math.max(leftHeight,rightHeight)1; } //寻找结点是否存在 public TreeNode find(TreeNode root,String val){ if (root null){ return null; } if(root.val.equals(val)){ return root; } TreeNode treeNode find(root.left,val); if(treeNode ! null){ return treeNode; } return find(root.right,val); } }测试类public static void main(String[] args) { TreeNode A new TreeNode(A); TreeNode B new TreeNode(B); TreeNode C new TreeNode(C); TreeNode D new TreeNode(D); TreeNode E new TreeNode(E); TreeNode F new TreeNode(F); TreeNode G new TreeNode(G); TreeNode H new TreeNode(H); //进行连接 A.left B; A.right C; B.left D; B.right E; C.left F; C.right G; E.right H; // 此时的结构为: // A // / \ // B C // / \ / \ // D E F G // \ // H }这里OJ题的前序遍历有返回值可以对比一下上面void的写法:接收返回值的前序遍历三、树的练习题题目由易到难层层递进狠狠递归1、相同的树判断两个树是否相同从判断结点上可以分为三种情况即注释使用前序遍历从根开始判断再到左子树最后到右子树//相同的树 public boolean isSameTree(TreeNode p, TreeNode q) { //一个为空另一个不为空 if(p null q ! null || p ! null q null){ return false; } //两个都是空 if (p null q null){ return true; } //两个都不为空可以想想为什么使用! if(p.val ! q.val){ return false; } //两棵树左子树右子树都相同 return isSameTree(p.left,q.left)isSameTree(p.right,q.right); }2、另一棵树的子树利用第一题的判断整棵树的方法以一棵树作为根让比较树与其根、左子树、右子树分别比较这三者只要一个相同即可//另一棵树的子树 public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(root null){ return false; } if(isSameTree(root,subRoot)){ return true; } return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot); }3、反转二叉树该题有两种写法一、使用前序遍历的思路由根开始交换然后左子树右子树二、后序遍历左右子树交换完成直接把原来根结点的左右子树交换即可//反转二叉树1 //前序遍历写法 public TreeNode flipTree(TreeNode root) { if(root null){ return null; } //1、访问当前节点交换地址 TreeNode tmp; tmp root.left; root.left root.right; root.right tmp; //2、反转左子树 flipTree(root.left); //3、反转右子树 flipTree(root.right); return root; }//反转二叉树2 //后序遍历写法 public TreeNode flipTree2(TreeNode root) { if(root null){ return null; } //左子树遍历 TreeNode left flipTree2(root.left); //右子树遍历 TreeNode right flipTree2(root.right); //交换操作 root.left right; root.right left; return root; }4、平衡二叉树时间复杂度为O(n^2)的写法//平衡二叉树 public boolean isBalanced(TreeNode root) { if(root null){ return true; } int x1 getMaxHeight2(root.left); int x2 getMaxHeight2(root.right); return Math.abs(x1-x2)1 isBalanced(root.left)isBalanced(root.right); } //二叉树的高度 public int getMaxHeight2(TreeNode root){ if (root null){ return 0; } int leftHeight getMaxHeight2(root.left); int rightHeight getMaxHeight2(root.right); return Math.max(leftHeight,rightHeight)1; }嵌套调用递归方法反复执行了一部分逻辑时间复杂度较高时间复杂度为O(n)的写法//平衡二叉树 //此时时间复杂度是n的平方 public boolean isBalanced(TreeNode root) { if(root null){ return true; } // int x1 getMaxHeight2(root.left); // int x2 getMaxHeight2(root.right); // // if(x1 -1 || x2 -1 || Math.abs(x1-x2)1){ // return false; // }else { // return true; // } return getMaxHeight2(root) 0; } //二叉树的高度 public int getMaxHeight2(TreeNode root){ if (root null){ return 0; } //最下方算式返回到上一级如果是负数就返回-1 int leftHeight getMaxHeight2(root.left); if(leftHeight0){ return -1; } int rightHeight getMaxHeight2(root.right); if(rightHeight0){ return -1; } if(Math.abs(leftHeight-rightHeight)1){ return -1; }else { return Math.max(leftHeight,rightHeight)1; } }这里注释掉了自己比较冗杂的写法因为事实上整体的递归逻辑都在getMaxHeight2这个方法里面了5、判断对称二叉树判断是否对称本质就是 左的左与右的右以及左的右与右的左比较//对称二叉树 public boolean checkSymmetricTree(TreeNode root) { if (root null){ return true; } return checkSymmetricTree2(root.left,root.right); } public boolean checkSymmetricTree2(TreeNode leftRoot,TreeNode rightRoot) { if(leftRoot null rightRoot ! null || leftRoot ! null rightRoot null){ return false; } if (leftRoot null rightRoot null){ return true; } if(leftRoot.val ! rightRoot.val){ return false; } return checkSymmetricTree2(leftRoot.left,rightRoot.right) checkSymmetricTree2(leftRoot.right,rightRoot.left); }递归的精髓就在于关注好当前结点尽量少试图每次都将递归的过程在脑海里模拟一遍6、层序遍历没有返回值的层序遍历//层序遍历 public void levelOrder(TreeNode root) { if(root null){ return; } QueueTreeNode q new LinkedList(); q.offer(root); while (!q.isEmpty()){ //记录当前结点 TreeNode cur q.poll(); System.out.println(cur.val); if(cur.left ! null){ q.offer(cur.left); } if (cur.right ! null){ q.offer(cur.right); } } }有返回值的层序遍历//层序遍历 public ListListInteger levelOrder(TreeNode root) { ListListInteger vessel new LinkedList(); if(root null){ return vessel; } QueueTreeNode q new LinkedList(); q.offer(root); while (!q.isEmpty()) { ListInteger l new LinkedList(); //队列里的元素个数 int size q.size(); while (size ! 0) { //记录当前结点 TreeNode cur q.poll(); l.add(cur.val); if (cur.left ! null) { q.offer(cur.left); } if (cur.right ! null) { q.offer(cur.right); } size--; } vessel.add(l); } return vessel; }将元素不断放入队列中同一层的元素出队放入到当前层链表处理完当前层数的所有元素后将这一层的链表放到大链表中一直到队列为空7、判断完全二叉树层序遍历的一个小变种核心在于当cur变成null的时候检查队列里是否有非空元素//判断完全二叉树 public boolean isCompleteTree(TreeNode root) { if(root null){ return true; } QueueTreeNode q new LinkedList(); q.offer(root); while (!q.isEmpty()){ TreeNode cur q.poll(); //此时其它所有子树的左右节点都已经入队过了(包括null) if(cur null){ break; } q.offer(cur.left); q.offer(cur.right); } //检查队列中是否存在非空元素存在则不是完全二叉树 while (!q.isEmpty()){ TreeNode top q.peek(); if(top ! null){ return false; } q.poll(); } return true; }8、二叉树的最近公共祖先递归的写法在于搞清楚p与q位置的三种情况//二叉树最近的公共祖先 //递归写法 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root null){ return null; } if(root p || root q){ return root; } TreeNode left lowestCommonAncestor(root.left,p,q); TreeNode right lowestCommonAncestor(root.right,p,q); //p与q分别在根节点两侧 if(left ! null right ! null){ return root; }else if(left ! null){ //p与q都在左侧 return left; }else if(right ! null){ //p与q都在右侧 return right; }else { return null; } }迭代的写法有点类似之前的链表相交关键在于分别找到p与q各自的路径将路径存放到栈里面先让两个栈长度相等判断一起弹出元素若相等则为最近公共祖先//迭代写法 public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){ StackTreeNode s1 new Stack(); StackTreeNode s2 new Stack(); //要从根结点开始处理 getPath(root,p,s1); getPath(root,q,s2); //弹出多余部分size相同的时候找到pop出的相同结点 int size1 s1.size(); int size2 s2.size(); int size s1.size()-s2.size(); if(size 0){ while (size2 ! size1){ s2.pop(); size2--; } }else { while (size1 ! size2){ s1.pop(); size1--; } } while (size1 ! 0 ){ TreeNode m s1.pop(); TreeNode n s2.pop(); if(m n){ return m; } } return null; } //核心方法 //拿到路径的每一个元素 public boolean getPath(TreeNode root,TreeNode node,StackTreeNode s){ if(root null){ return false; } //将根节点放入栈 s.push(root); if(root node){ return true; } boolean flag1 getPath(root.left,node,s); if (flag1 true){ return true; } boolean flag2 getPath(root.right,node,s); if (flag2 true){ return true; } //弹出非路径结点 //即当前结点以及左右子树都没有目标结点 s.pop(); return false; }9、从前序中序序列中获取二叉树10、从中序后序遍历中获取二叉树整体逻辑1、自己创建一个带有四个参数的递归方法四个参数分别是​​​​​​中序数组、后序数组中序数组的开始指针inBegin、中序数组的结束指针inEnd2、定义一个后序数组的全局指针 postIndex初始指向后序数组的最后一个元素3、创建一个查找方法用于找到后序数组当前元素在中序数组中的位置。该方法参数包括中序数组、目标元素即当前后序指针指向的值中序数组的开始指针、中序数组的结束指针4、在递归方法中的执行步骤将后序数组当前指针指向的元素创建为根节点调用查找方法获取该根节点在中序数组中的下标inorderIndex后序数组指针前移postIndex--注意是从右向左移动先递归构建右子树范围inorderIndex1到inEnd再递归构建左子树范围inBegin到inorderIndex-1返回根节点5、终止条件当inBegin inEnd时返回nullint preIndex 0; //根据前序中序遍历构造二叉树 public TreeNode buildTree(int[] preorder, int[] inorder) { //初始范围整个中序数组即 0 到 length-1 return buildTreeChild(preorder, inorder, 0, inorder.length - 1); } public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegin, int inEnd) { //终止条件 if(inBegin inEnd){ return null; } //1、从前序数组中取当前指针的值作为根节点 TreeNode root new TreeNode(preorder[preIndex]); //2、找到当前前序序列根节点在中序序列里的下标 int inorderIndex findRootIndex(inorder,preorder[preIndex],inBegin,inEnd); //3、前序序列指针前移找到下一个根节点递归时创建 preIndex; //4、递归左右子树 //注意左右子树的范围 root.left buildTreeChild(preorder,inorder,inBegin,inorderIndex-1); root.right buildTreeChild(preorder,inorder,inorderIndex1,inEnd); return root; } //负责找到当前前序序列根节点在中序序列里的下标 public int findRootIndex(int[] inorder, int key, int inBegin, int inEnd) { for (int i inBegin; i inEnd; i) { if (inorder[i] key){ return i; } } return -1; }12、根据二叉树创建字符串以及前、中、后序遍历的非递归写法也可以看看本章完