企业官网建设流程全解析

网站制作的主要流程,网络科技公司主要做什么,网站增长期怎么做,wordpress登录密码重置Morris遍历: 二叉树之前的遍历方式有空间浪费的问题(递归实现也会占中栈空间)。Morris遍历时间复杂度O(N)#xff0c;额外空间复杂度O(1)#xff0c;通过利用原树中大量空闲指针的方式#xff0c;达到节省空间的目的 1、Morris遍历概述 Morris遍历 二叉树之前的遍历方式有空…Morris遍历: 二叉树之前的遍历方式有空间浪费的问题(递归实现也会占中栈空间)。Morris遍历时间复杂度O(N)额外空间复杂度O(1)通过利用原树中大量空闲指针的方式达到节省空间的目的1、Morris遍历概述Morris遍历二叉树之前的遍历方式有空间浪费的问题(递归实现也会占中栈空间)Morris遍历时间复杂度O(N)额外空间复杂度O(1)通过利用原树中大量空闲指针的方式达到节省空间的目的Morris遍历过程假设来到当前节点cur开始时cur来到头节点位置1如果cur没有左孩子cur向右移动(cur cur.right)2如果cur有左孩子找到左子树上最右的节点mostRight2.1如果mostRight的右指针指向空让其指向cur然后cur向左移动(cur cur.left)2.2如果mostRight的右指针指向cur让其指向null然后cur向右移动(cur cur.right)3cur为空时遍历停止Morris遍历的特点1Morris遍历的过程中cur指针会移动到每一个节点也就是每个节点都会被cur访问到但是有个规律如果一个节点有左孩子这个节点会被cur访问2次如何区分是第2次访问到判断左树最右侧的节点是否指向自己如果指向自己说明是第2次访问到。如果一个节点没有左孩子这个节点会被cur访问1次cur指针的指向顺序就是Morris遍历的顺序。2Morris遍历的过程中存在寻找mostRight的过程所以每一个叶子节点都会被mostRight访问到作为父节点的左孩子的叶子节点会在寻找父节点的左孩子的有边界的时候被mostRight访问到因为此时只有它一个节点对于作为父节点的右孩子的叶子节点会在父节点的父节点在寻找父节点的有边界的时候被mostRight访问到要区分这个叶子节点是第一次被访问到还是第二次被访问到同样是判断左树最右侧的节点是否指向自己如果指向自己说明是第2次访问到。通常所说的被访问到是指cur访问到而判断是第一次访问到还是第二次访问到是根据mostRight的指向来判断的。对于关注叶子节点的题目我们要知道的是叶子节点实际上都是可以被mostRight访问到的Morris遍历的应用基于基本的Morris遍历流程通过在不同时机执行“访问”操作如打印节点值可以分别实现前序、中序和后序遍历。1前序遍历cur第一次到达该节点时就访问顺序为根节点 - 左子树 - 右子树2中序遍历cur第二次到达该节点时即从左子树返回时才访问顺序为左子树 - 根节点 - 右子树3后序遍历cur第二次到达该节点时逆序打印该节点左子树的右边界。最后单独逆序打印整棵树的右边界2、Morris遍历的实现2.1、Morris遍历模板Morris遍历代码模板思路根据Morris遍历的过程写出的代码模板1如果cur没有左孩子cur向右移动(cur cur.right)2如果cur有左孩子找到左子树上最右的节点mostRight2.1如果mostRight的右指针指向空让其指向cur然后cur向左移动(cur cur.left)2.2如果mostRight的右指针指向cur让其指向null然后cur向右移动(cur cur.right)3cur为空时遍历停止示例如下面这个二叉树Morris遍历的顺序为a - b - d - b - e - a - c - f - c - g/** * Morris遍历代码模板 * 思路 * 根据Morris遍历的过程写出的代码模板 * 1如果cur没有左孩子cur向右移动(cur cur.right) * 2如果cur有左孩子找到左子树上最右的节点mostRight * 2.1如果mostRight的右指针指向空让其指向cur然后cur向左移动(cur cur.left) * 2.2如果mostRight的右指针指向cur让其指向null然后cur向右移动(cur cur.right) * 3cur为空时遍历停止 * 示例 * 如下面这个二叉树 * ............a * ........../...\ * .........b.....c * ......../.\.../.\ * .......d..e..f...g * Morris遍历的顺序为a - b - d - b - e - a - c - f - c - g */publicstaticvoidmorris(Nodehead){if(headnull){return;}// cur 指针指向当前访问的节点初始为头节点Nodecurhead;// mostRight 指针,指向左子树最右侧的节点初始为nullNodemostRightnull;// 开始遍历对应过程的3cur为空时遍历停止while(cur!null){// 先将mostRight指针指向当前节点的左孩子这样就可以根据mostRight是否为空判断是否有左孩子mostRightcur.left;if(mostRight!null){// 有左孩子这个节点会被访问2次 // 依据过程 2如果cur有左孩子找到左子树上最右的节点mostRight// 找到左子树的最右侧节点没有右子树或者上一次改成了指向自己都要停止while(mostRight.right!nullmostRight.right!cur){mostRightmostRight.right;}if(mostRight.rightnull){// 第一次到达左子树的最右侧节点对应过程2.1mostRight.rightcur;curcur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点对应过程2.2mostRight.rightnull;}}// else{// // 没有左孩子这个节点会被访问1次如果要单独挑出被访问一次的节点可以加上else在这里判断// }// 对于过程 1和2.2即没有左孩子或者第二次访问节点都会执行到这里接下来访问当前节点的右孩子curcur.right;}}2.2、Morris遍历实现前序遍历Morris遍历实现前序遍历思路cur第一次到达该节点时就访问顺序为根节点 - 左子树 - 右子树因为Morris遍历的过程中有左子树的节点会被访问两次没有的会被访问1次所以要挑出第一次访问的时候就有两个地方1 对于有左子树的节点第一次访问是根据mostRight的right指针为空的时候2 对于没有左子树的节点第一次访问是根据cur的左孩子为空的时候/** * Morris遍历实现前序遍历 * 思路 * cur第一次到达该节点时就访问顺序为根节点 - 左子树 - 右子树 * 因为Morris遍历的过程中有左子树的节点会被访问两次没有的会被访问1次 * 所以要挑出第一次访问的时候就有两个地方 * 1 对于有左子树的节点第一次访问是根据mostRight的right指针为空的时候 * 2 对于没有左子树的节点第一次访问是根据cur的左孩子为空的时候 */publicstaticvoidmorrisPre(Nodehead){if(headnull){return;}System.out.print(morrisPre: );Nodecurhead;NodemostRightnull;while(cur!null){mostRightcur.left;if(mostRight!null){// 有左子树while(mostRight.right!nullmostRight.right!cur){mostRightmostRight.right;}if(mostRight.rightnull){// 第一次到达左子树的最右侧节点对应过程2.1System.out.print(cur.value );mostRight.rightcur;curcur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点对应过程2.2mostRight.rightnull;}}else{// 没有左子树第一次访问是根据cur的左孩子为空的时候System.out.print(cur.value );}curcur.right;}System.out.println();}2.3、Morris遍历实现中序遍历Morris遍历实现中序遍历思路cur第二次到达该节点时即从左子树返回时才访问顺序为左子树 - 根节点 - 右子树因为Morris遍历的过程中有左子树的节点会被访问两次没有的会被访问1次对于只访问一次的节点就是直接访问了对于访问两次的节点是要在第二次访问根据Morris的遍历代码可以看出无论是没有左树还是第二次访问都会走到最后指向右节点的位置所以我们只需要在指向右节点之前访问信息就可以了。/** * Morris遍历实现中序遍历 * 思路 * cur第二次到达该节点时即从左子树返回时才访问顺序为左子树 - 根节点 - 右子树 * 因为Morris遍历的过程中有左子树的节点会被访问两次没有的会被访问1次 * 对于只访问一次的节点就是直接访问了对于访问两次的节点是要在第二次访问 * 根据Morris的遍历代码可以看出无论是没有左树还是第二次访问都会走到最后指向右节点的位置 * 所以我们只需要在指向右节点之前访问信息就可以了。 */publicstaticvoidmorrisIn(Nodehead){if(headnull){return;}System.out.print(morrisIn : );Nodecurhead;NodemostRightnull;while(cur!null){mostRightcur.left;if(mostRight!null){// 有左子树while(mostRight.right!nullmostRight.right!cur){mostRightmostRight.right;}if(mostRight.rightnull){// 第一次到达左子树的最右侧节点对应过程2.1mostRight.rightcur;curcur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点对应过程2.2mostRight.rightnull;}}// 没有左孩子和第二次到达都会走到这里System.out.print(cur.value );curcur.right;}System.out.println();}2.4、Morris遍历实现后序遍历Morris遍历实现后序遍历思路cur第二次到达该节点时逆序打印该节点左子树的右边界。最后单独逆序打印整棵树的右边界根据Morris遍历的过程第二次到达该节点的位置很容易找到麻烦的是如何逆序打印该节点左子树的右边界。我们可以将左子树的有边界看成是一个链表先用反转链表的方式将其转过来然后打印完成以后再反转回来。/** * Morris遍历实现后序遍历 * 思路 * cur第二次到达该节点时逆序打印该节点左子树的右边界。最后单独逆序打印整棵树的右边界 * 根据Morris遍历的过程第二次到达该节点的位置很容易找到 * 麻烦的是如何逆序打印该节点左子树的右边界。 * 我们可以将左子树的有边界看成是一个链表先用反转链表的方式将其转过来然后打印完成以后再反转回来。 */publicstaticvoidmorrisPos(Nodehead){if(headnull){return;}System.out.print(morrisPos: );Nodecurhead;NodemostRightnull;while(cur!null){mostRightcur.left;if(mostRight!null){// 有左子树while(mostRight.right!nullmostRight.right!cur){mostRightmostRight.right;}if(mostRight.rightnull){// 第一次到达左子树的最右侧节点对应过程2.1mostRight.rightcur;curcur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点对应过程2.2mostRight.rightnull;// 逆序打印左子树的有边界printEdge(cur.left);}}curcur.right;}// 单独打印整棵树的有边界printEdge(head);System.out.println();}/** * 逆序打印右边界 */publicstaticvoidprintEdge(Nodehead){// 先逆序右边界组成的链NodetailreverseEdge(head);// 此时打印就是逆序的Nodecurtail;while(cur!null){System.out.print(cur.value );curcur.right;}// 最后再逆序回来恢复树的形状reverseEdge(tail);}/** * 逆序有边界组成的链 */publicstaticNodereverseEdge(Nodefrom){Nodeprenull;Nodenextnull;while(from!null){nextfrom.right;from.rightpre;prefrom;fromnext;}returnpre;}2.5、Morris遍历判断是否为二叉搜索树Morris遍历判断是否为二叉搜索树思路二叉搜索树的左右子树都要比其父节点大我们可以用中序遍历二叉树的方式用一个变量记录上一个访问的节点的值如果当前节点的值小于等于上一个节点的值说明不是二叉搜索树。/** * Morris遍历判断是否为二叉搜索树 * 思路 * 二叉搜索树的左右子树都要比其父节点大 * 我们可以用中序遍历二叉树的方式用一个变量记录上一个访问的节点的值 * 如果当前节点的值小于等于上一个节点的值说明不是二叉搜索树。 */publicstaticbooleanisBST(Nodehead){if(headnull){returntrue;}Nodecurhead;NodemostRightnull;// 前一个访问的节点的值Integerprenull;booleananstrue;while(cur!null){mostRightcur.left;if(mostRight!null){while(mostRight.right!nullmostRight.right!cur){mostRightmostRight.right;}if(mostRight.rightnull){mostRight.rightcur;curcur.left;continue;}else{mostRight.rightnull;}}if(pre!nullprecur.value){ansfalse;}// 中序遍历的方式所以只需要在这里改pre的值即可precur.value;curcur.right;}returnans;}整体代码和测试如下/** * Morris遍历 * 二叉树之前的遍历方式有空间浪费的问题(递归实现也会占中栈空间) * Morris遍历时间复杂度O(N)额外空间复杂度O(1)通过利用原树中大量空闲指针的方式达到节省空间的目的 * br * Morris遍历过程 * 假设来到当前节点cur开始时cur来到头节点位置 * 1如果cur没有左孩子cur向右移动(cur cur.right) * 2如果cur有左孩子找到左子树上最右的节点mostRight * 2.1如果mostRight的右指针指向空让其指向cur然后cur向左移动(cur cur.left) * 2.2如果mostRight的右指针指向cur让其指向null然后cur向右移动(cur cur.right) * 3cur为空时遍历停止 * br * Morris遍历的特点 * 1Morris遍历的过程中cur指针会移动到每一个节点也就是每个节点都会被cur访问到但是有个规律 * 如果一个节点有左孩子这个节点会被cur访问2次如何区分是第2次访问到判断左树最右侧的节点是否指向自己如果指向自己说明是第2次访问到。 * 如果一个节点没有左孩子这个节点会被cur访问1次 * cur指针的指向顺序就是Morris遍历的顺序。 * 2Morris遍历的过程中存在寻找mostRight的过程所以每一个叶子节点都会被mostRight访问到 * 作为父节点的左孩子的叶子节点会在寻找父节点的左孩子的有边界的时候被mostRight访问到因为此时只有它一个节点 * 对于作为父节点的右孩子的叶子节点会在父节点的父节点在寻找父节点的有边界的时候被mostRight访问到 * 要区分这个叶子节点是第一次被访问到还是第二次被访问到同样是判断左树最右侧的节点是否指向自己如果指向自己说明是第2次访问到。 * 通常所说的被访问到是指cur访问到而判断是第一次访问到还是第二次访问到是根据mostRight的指向来判断的。 * 对于关注叶子节点的题目我们要知道的是叶子节点实际上都是可以被mostRight访问到的 * br * Morris遍历的应用 * 基于基本的Morris遍历流程通过在不同时机执行“访问”操作如打印节点值可以分别实现前序、中序和后序遍历。 * 1前序遍历cur第一次到达该节点时就访问顺序为根节点 - 左子树 - 右子树 * 2中序遍历cur第二次到达该节点时即从左子树返回时才访问顺序为左子树 - 根节点 - 右子树 * 3后序遍历cur第二次到达该节点时逆序打印该节点左子树的右边界。最后单独逆序打印整棵树的右边界 */publicclassMorrisTraversal{/** * Morris遍历代码模板 * 思路 * 根据Morris遍历的过程写出的代码模板 * 1如果cur没有左孩子cur向右移动(cur cur.right) * 2如果cur有左孩子找到左子树上最右的节点mostRight * 2.1如果mostRight的右指针指向空让其指向cur然后cur向左移动(cur cur.left) * 2.2如果mostRight的右指针指向cur让其指向null然后cur向右移动(cur cur.right) * 3cur为空时遍历停止 * 示例 * 如下面这个二叉树 * ............a * ........../...\ * .........b.....c * ......../.\.../.\ * .......d..e..f...g * Morris遍历的顺序为a - b - d - b - e - a - c - f - c - g */publicstaticvoidmorris(Nodehead){if(headnull){return;}// cur 指针指向当前访问的节点初始为头节点Nodecurhead;// mostRight 指针,指向左子树最右侧的节点初始为nullNodemostRightnull;// 开始遍历对应过程的3cur为空时遍历停止while(cur!null){// 先将mostRight指针指向当前节点的左孩子这样就可以根据mostRight是否为空判断是否有左孩子mostRightcur.left;if(mostRight!null){// 有左孩子这个节点会被访问2次 // 依据过程 2如果cur有左孩子找到左子树上最右的节点mostRight// 找到左子树的最右侧节点没有右子树或者上一次改成了指向自己都要停止while(mostRight.right!nullmostRight.right!cur){mostRightmostRight.right;}if(mostRight.rightnull){// 第一次到达左子树的最右侧节点对应过程2.1mostRight.rightcur;curcur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点对应过程2.2mostRight.rightnull;}}// else{// // 没有左孩子这个节点会被访问1次如果要单独挑出被访问一次的节点可以加上else在这里判断// }// 对于过程 1和2.2即没有左孩子或者第二次访问节点都会执行到这里接下来访问当前节点的右孩子curcur.right;}}/** * Morris遍历实现前序遍历 * 思路 * cur第一次到达该节点时就访问顺序为根节点 - 左子树 - 右子树 * 因为Morris遍历的过程中有左子树的节点会被访问两次没有的会被访问1次 * 所以要挑出第一次访问的时候就有两个地方 * 1 对于有左子树的节点第一次访问是根据mostRight的right指针为空的时候 * 2 对于没有左子树的节点第一次访问是根据cur的左孩子为空的时候 */publicstaticvoidmorrisPre(Nodehead){if(headnull){return;}System.out.print(morrisPre: );Nodecurhead;NodemostRightnull;while(cur!null){mostRightcur.left;if(mostRight!null){// 有左子树while(mostRight.right!nullmostRight.right!cur){mostRightmostRight.right;}if(mostRight.rightnull){// 第一次到达左子树的最右侧节点对应过程2.1System.out.print(cur.value );mostRight.rightcur;curcur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点对应过程2.2mostRight.rightnull;}}else{// 没有左子树第一次访问是根据cur的左孩子为空的时候System.out.print(cur.value );}curcur.right;}System.out.println();}/** * Morris遍历实现中序遍历 * 思路 * cur第二次到达该节点时即从左子树返回时才访问顺序为左子树 - 根节点 - 右子树 * 因为Morris遍历的过程中有左子树的节点会被访问两次没有的会被访问1次 * 对于只访问一次的节点就是直接访问了对于访问两次的节点是要在第二次访问 * 根据Morris的遍历代码可以看出无论是没有左树还是第二次访问都会走到最后指向右节点的位置 * 所以我们只需要在指向右节点之前访问信息就可以了。 */publicstaticvoidmorrisIn(Nodehead){if(headnull){return;}System.out.print(morrisIn : );Nodecurhead;NodemostRightnull;while(cur!null){mostRightcur.left;if(mostRight!null){// 有左子树while(mostRight.right!nullmostRight.right!cur){mostRightmostRight.right;}if(mostRight.rightnull){// 第一次到达左子树的最右侧节点对应过程2.1mostRight.rightcur;curcur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点对应过程2.2mostRight.rightnull;}}// 没有左孩子和第二次到达都会走到这里System.out.print(cur.value );curcur.right;}System.out.println();}/** * Morris遍历实现后序遍历 * 思路 * cur第二次到达该节点时逆序打印该节点左子树的右边界。最后单独逆序打印整棵树的右边界 * 根据Morris遍历的过程第二次到达该节点的位置很容易找到 * 麻烦的是如何逆序打印该节点左子树的右边界。 * 我们可以将左子树的有边界看成是一个链表先用反转链表的方式将其转过来然后打印完成以后再反转回来。 */publicstaticvoidmorrisPos(Nodehead){if(headnull){return;}System.out.print(morrisPos: );Nodecurhead;NodemostRightnull;while(cur!null){mostRightcur.left;if(mostRight!null){// 有左子树while(mostRight.right!nullmostRight.right!cur){mostRightmostRight.right;}if(mostRight.rightnull){// 第一次到达左子树的最右侧节点对应过程2.1mostRight.rightcur;curcur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点对应过程2.2mostRight.rightnull;// 逆序打印左子树的有边界printEdge(cur.left);}}curcur.right;}// 单独打印整棵树的有边界printEdge(head);System.out.println();}/** * 逆序打印右边界 */publicstaticvoidprintEdge(Nodehead){// 先逆序右边界组成的链NodetailreverseEdge(head);// 此时打印就是逆序的Nodecurtail;while(cur!null){System.out.print(cur.value );curcur.right;}// 最后再逆序回来恢复树的形状reverseEdge(tail);}/** * 逆序有边界组成的链 */publicstaticNodereverseEdge(Nodefrom){Nodeprenull;Nodenextnull;while(from!null){nextfrom.right;from.rightpre;prefrom;fromnext;}returnpre;}/** * Morris遍历判断是否为二叉搜索树 * 思路 * 二叉搜索树的左右子树都要比其父节点大 * 我们可以用中序遍历二叉树的方式用一个变量记录上一个访问的节点的值 * 如果当前节点的值小于等于上一个节点的值说明不是二叉搜索树。 */publicstaticbooleanisBST(Nodehead){if(headnull){returntrue;}Nodecurhead;NodemostRightnull;// 前一个访问的节点的值Integerprenull;booleananstrue;while(cur!null){mostRightcur.left;if(mostRight!null){while(mostRight.right!nullmostRight.right!cur){mostRightmostRight.right;}if(mostRight.rightnull){mostRight.rightcur;curcur.left;continue;}else{mostRight.rightnull;}}if(pre!nullprecur.value){ansfalse;}// 中序遍历的方式所以只需要在这里改pre的值即可precur.value;curcur.right;}returnans;}/** * 二叉树的节点定义 */publicstaticclassNode{publicintvalue;Nodeleft;Noderight;publicNode(intdata){this.valuedata;}}publicstaticvoidmain(String[]args){NodeheadnewNode(4);head.leftnewNode(2);head.rightnewNode(6);head.left.leftnewNode(1);head.left.rightnewNode(3);head.right.leftnewNode(5);head.right.rightnewNode(7);printTree(head);morrisPre(head);morrisIn(head);morrisPos(head);printTree(head);System.out.println(isBST(head));}// for test -- print treepublicstaticvoidprintTree(Nodehead){System.out.println(Binary Tree:);printInOrder(head,0,H,17);System.out.println();}publicstaticvoidprintInOrder(Nodehead,intheight,Stringto,intlen){if(headnull){return;}printInOrder(head.right,height1,v,len);Stringvaltohead.valueto;intlenMval.length();intlenL(len-lenM)/2;intlenRlen-lenM-lenL;valgetSpace(lenL)valgetSpace(lenR);System.out.println(getSpace(height*len)val);printInOrder(head.left,height1,^,len);}publicstaticStringgetSpace(intnum){Stringspace ;StringBufferbufnewStringBuffer();for(inti0;inum;i){buf.append(space);}returnbuf.toString();}}3、题目求二叉树的最小深度题目求二叉树的最小深度给定一个二叉树找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明叶子节点是指没有子节点的节点。测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree3.1、二叉树的递归套路实现方法二叉树的递归套路实现方法思路根据二叉树的递归套路我们需要最小的深度那就要像左右节点要他们各自最小的深度要到以后取他们最小的深度再加上1就是以x为头的树的最小深度提交时方法名改为minDepth/** * 二叉树的递归套路实现方法 * 思路 * 根据二叉树的递归套路我们需要最小的深度那就要像左右节点要他们各自最小的深度 * 要到以后取他们最小的深度再加上1就是以x为头的树的最小深度 * 提交时方法名改为minDepth */publicstaticintminDepth(TreeNodehead){if(headnull){return0;}returnminDepthProcess(head);}/** * 递归函数的定义返回x为头的树最小深度是多少 */publicstaticintminDepthProcess(TreeNodex){if(x.leftnullx.rightnull){// 叶节点返回1return1;}// 左右子树起码有一个不为空intleftHInteger.MAX_VALUE;if(x.left!null){leftHminDepthProcess(x.left);}intrightHInteger.MAX_VALUE;if(x.right!null){rightHminDepthProcess(x.right);}return1Math.min(leftH,rightH);}3.2、Morris遍历实现方法Morris遍历实现方法思路要判断一个数的深度即是从根节点到叶子节点的距离然后取一个最小值即可。根据Morris遍历我们知道叶子节点都会被mostRight指针遍历到所以这个是可以通过mostRight指针来判断的。我们只需要记录每一个节点的深度就能统计出到叶子节点的距离。然后用一个变量取到他们中的最小值即可。这里有两个问题1根据Morris遍历有些节点会被访问两次而且是从叶子节点直接转到上层深度变化如何处理对于这个问题因为第一次到达叶子节点的时候我们是用了mostRight来找子节点的最右节点可以在这个过程中统计出子节点到最右节点的距离然后到第二次访问的时候直接减去这个距离即可还原原来节点的深度。2根据Morris遍历我们访问到最后一个节点的时候就直接退出了所以整棵树的最右边这条边是没有统计的。所以我们在整体统计完成以后需要单独统计一下整棵树的最右边的深度需要的时候考虑上最小值即可。提交时方法名改为minDepth/** * Morris遍历实现方法 * 思路 * 要判断一个数的深度即是从根节点到叶子节点的距离然后取一个最小值即可。 * 根据Morris遍历我们知道叶子节点都会被mostRight指针遍历到所以这个是可以通过mostRight指针来判断的。 * 我们只需要记录每一个节点的深度就能统计出到叶子节点的距离。然后用一个变量取到他们中的最小值即可。 * 这里有两个问题 * 1根据Morris遍历有些节点会被访问两次而且是从叶子节点直接转到上层深度变化如何处理 * 对于这个问题因为第一次到达叶子节点的时候我们是用了mostRight来找子节点的最右节点可以在这个过程中统计出子节点到最右节点的距离 * 然后到第二次访问的时候直接减去这个距离即可还原原来节点的深度。 * 2根据Morris遍历我们访问到最后一个节点的时候就直接退出了所以整棵树的最右边这条边是没有统计的。 * 所以我们在整体统计完成以后需要单独统计一下整棵树的最右边的深度需要的时候考虑上最小值即可。 * 提交时方法名改为minDepth */publicstaticintminDepth(TreeNodehead){if(headnull){return0;}TreeNodecurhead;TreeNodemostRightnull;// 记录当前节点的深度的变量intcurLevel0;// 记录最小高度的变量intminHeightInteger.MAX_VALUE;while(cur!null){mostRightcur.left;if(mostRight!null){// 统计到左子树最右边节点的距离intrightBoardSize1;while(mostRight.right!nullmostRight.right!cur){rightBoardSize;mostRightmostRight.right;}if(mostRight.rightnull){// 第一次到达深度加1curLevel;mostRight.rightcur;curcur.left;continue;}else{// 第二次到达,此时的深度还没有减去右子树的深度所以是子树最右侧节点的深度需要统计到整体的里面if(mostRight.leftnull){minHeightMath.min(minHeight,curLevel);}// 减去右子树的深度还原到当前节点的深度curLevel-rightBoardSize;mostRight.rightnull;}}else{// 只有一次到达的节点直接统计深度深度加1curLevel;}curcur.right;}// 单独统计整棵树的最右边的深度intfinalRight1;curhead;while(cur.right!null){finalRight;curcur.right;}// 整个树的最右节点是一个叶子节点的时候需要将最优节点的高度加进去// 如果不是叶子节点说明有左节点肯定比finalRight大。所以不能把finalRight加进去。if(cur.leftnullcur.rightnull){minHeightMath.min(minHeight,finalRight);}returnminHeight;}后记个人学习总结笔记不能保证非常详细轻喷