news 2026/4/16 18:04:04

【算法笔记】二叉树的Morris遍历

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
【算法笔记】二叉树的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有左孩子，找到左子树上最右的节点mostRight：
    • 2.1）如果mostRight的右指针指向空，让其指向cur，然后cur向左移动(cur = cur.left)
    • 2.2）如果mostRight的右指针指向cur，让其指向null，然后cur向右移动(cur = cur.right)
    • 3）cur为空时遍历停止

  • Morris遍历的特点：
    • 1）Morris遍历的过程中，cur指针会移动到每一个节点，也就是每个节点都会被cur访问到，但是有个规律：
    • 如果一个节点有左孩子，这个节点会被cur访问2次，如何区分是第2次访问到：判断左树最右侧的节点是否指向自己，如果指向自己，说明是第2次访问到。
    • 如果一个节点没有左孩子，这个节点会被cur访问1次，
    • cur指针的指向顺序，就是Morris遍历的顺序。
    • 2）Morris遍历的过程中，存在寻找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有左孩子，找到左子树上最右的节点mostRight：

    • 2.1）如果mostRight的右指针指向空，让其指向cur，然后cur向左移动(cur = cur.left)

    • 2.2）如果mostRight的右指针指向cur，让其指向null，然后cur向右移动(cur = cur.right)

    • 3）cur为空时遍历停止

    • 示例：

    • 如下面这个二叉树：

    • 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) * 3）cur为空时遍历停止 * 示例： * 如下面这个二叉树： * ............a * ........../...\ * .........b.....c * ......../.\.../.\ * .......d..e..f...g * Morris遍历的顺序为：a -> b -> d -> b -> e -> a -> c -> f -> c -> g */publicstaticvoidmorris(Nodehead){if(head==null){return;}// cur 指针，指向当前访问的节点，初始为头节点Nodecur=head;// mostRight 指针,指向左子树最右侧的节点，初始为nullNodemostRight=null;// 开始遍历，对应过程的：3）cur为空时遍历停止while(cur!=null){// 先将mostRight指针指向当前节点的左孩子，这样就可以根据mostRight是否为空，判断是否有左孩子mostRight=cur.left;if(mostRight!=null){// 有左孩子，这个节点会被访问2次 ，// 依据过程 2）如果cur有左孩子，找到左子树上最右的节点mostRight// 找到左子树的最右侧节点，没有右子树或者上一次改成了指向自己，都要停止while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){// 第一次到达左子树的最右侧节点，对应过程2.1）mostRight.right=cur;cur=cur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点，对应过程2.2）mostRight.right=null;}}// else{// // 没有左孩子，这个节点会被访问1次，如果要单独挑出被访问一次的节点，可以加上else在这里判断// }// 对于过程 1）和2.2），即没有左孩子或者第二次访问节点，都会执行到这里，接下来访问当前节点的右孩子cur=cur.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(head==null){return;}System.out.print("morrisPre: ");Nodecur=head;NodemostRight=null;while(cur!=null){mostRight=cur.left;if(mostRight!=null){// 有左子树while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){// 第一次到达左子树的最右侧节点，对应过程2.1）System.out.print(cur.value+" ");mostRight.right=cur;cur=cur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点，对应过程2.2）mostRight.right=null;}}else{// 没有左子树，第一次访问是根据cur的左孩子为空的时候，System.out.print(cur.value+" ");}cur=cur.right;}System.out.println();}

2.3、Morris遍历实现中序遍历

  • Morris遍历实现中序遍历
  • 思路：
    • cur第二次到达该节点时（即从左子树返回时）才访问，顺序为：左子树 -> 根节点 -> 右子树
    • 因为Morris遍历的过程中，有左子树的节点会被访问两次，没有的会被访问1次，
    • 对于只访问一次的节点，就是直接访问了，对于访问两次的节点，是要在第二次访问，
    • 根据Morris的遍历代码可以看出，无论是没有左树还是第二次访问，都会走到最后指向右节点的位置，
    • 所以我们只需要在指向右节点之前访问信息就可以了。
/** * Morris遍历实现中序遍历 * 思路： * cur第二次到达该节点时（即从左子树返回时）才访问，顺序为：左子树 -> 根节点 -> 右子树 * 因为Morris遍历的过程中，有左子树的节点会被访问两次，没有的会被访问1次， * 对于只访问一次的节点，就是直接访问了，对于访问两次的节点，是要在第二次访问， * 根据Morris的遍历代码可以看出，无论是没有左树还是第二次访问，都会走到最后指向右节点的位置， * 所以我们只需要在指向右节点之前访问信息就可以了。 */publicstaticvoidmorrisIn(Nodehead){if(head==null){return;}System.out.print("morrisIn : ");Nodecur=head;NodemostRight=null;while(cur!=null){mostRight=cur.left;if(mostRight!=null){// 有左子树while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){// 第一次到达左子树的最右侧节点，对应过程2.1）mostRight.right=cur;cur=cur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点，对应过程2.2）mostRight.right=null;}}// 没有左孩子和第二次到达，都会走到这里System.out.print(cur.value+" ");cur=cur.right;}System.out.println();}

2.4、Morris遍历实现后序遍历

  • Morris遍历实现后序遍历
  • 思路：
    • cur第二次到达该节点时，逆序打印该节点左子树的右边界。最后，单独逆序打印整棵树的右边界，
    • 根据Morris遍历的过程，第二次到达该节点的位置很容易找到，
    • 麻烦的是如何逆序打印该节点左子树的右边界。
    • 我们可以将左子树的有边界看成是一个链表，先用反转链表的方式将其转过来，然后打印，完成以后再反转回来。
/** * Morris遍历实现后序遍历 * 思路： * cur第二次到达该节点时，逆序打印该节点左子树的右边界。最后，单独逆序打印整棵树的右边界， * 根据Morris遍历的过程，第二次到达该节点的位置很容易找到， * 麻烦的是如何逆序打印该节点左子树的右边界。 * 我们可以将左子树的有边界看成是一个链表，先用反转链表的方式将其转过来，然后打印，完成以后再反转回来。 */publicstaticvoidmorrisPos(Nodehead){if(head==null){return;}System.out.print("morrisPos: ");Nodecur=head;NodemostRight=null;while(cur!=null){mostRight=cur.left;if(mostRight!=null){// 有左子树while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){// 第一次到达左子树的最右侧节点，对应过程2.1）mostRight.right=cur;cur=cur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点，对应过程2.2）mostRight.right=null;// 逆序打印左子树的有边界printEdge(cur.left);}}cur=cur.right;}// 单独打印整棵树的有边界printEdge(head);System.out.println();}/** * 逆序打印右边界 */publicstaticvoidprintEdge(Nodehead){// 先逆序右边界组成的链Nodetail=reverseEdge(head);// 此时打印，就是逆序的Nodecur=tail;while(cur!=null){System.out.print(cur.value+" ");cur=cur.right;}// 最后再逆序回来，恢复树的形状reverseEdge(tail);}/** * 逆序有边界组成的链 */publicstaticNodereverseEdge(Nodefrom){Nodepre=null;Nodenext=null;while(from!=null){next=from.right;from.right=pre;pre=from;from=next;}returnpre;}

2.5、Morris遍历判断是否为二叉搜索树

  • Morris遍历判断是否为二叉搜索树
  • 思路：
    • 二叉搜索树的左右子树都要比其父节点大，
    • 我们可以用中序遍历二叉树的方式，用一个变量记录上一个访问的节点的值，
    • 如果当前节点的值小于等于上一个节点的值，说明不是二叉搜索树。
/** * Morris遍历判断是否为二叉搜索树 * 思路： * 二叉搜索树的左右子树都要比其父节点大， * 我们可以用中序遍历二叉树的方式，用一个变量记录上一个访问的节点的值， * 如果当前节点的值小于等于上一个节点的值，说明不是二叉搜索树。 */publicstaticbooleanisBST(Nodehead){if(head==null){returntrue;}Nodecur=head;NodemostRight=null;// 前一个访问的节点的值Integerpre=null;booleanans=true;while(cur!=null){mostRight=cur.left;if(mostRight!=null){while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){mostRight.right=cur;cur=cur.left;continue;}else{mostRight.right=null;}}if(pre!=null&&pre>=cur.value){ans=false;}// 中序遍历的方式，所以只需要在这里改pre的值即可pre=cur.value;cur=cur.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) * 3）cur为空时遍历停止 * <br> * Morris遍历的特点： * 1）Morris遍历的过程中，cur指针会移动到每一个节点，也就是每个节点都会被cur访问到，但是有个规律： * 如果一个节点有左孩子，这个节点会被cur访问2次，如何区分是第2次访问到：判断左树最右侧的节点是否指向自己，如果指向自己，说明是第2次访问到。 * 如果一个节点没有左孩子，这个节点会被cur访问1次， * cur指针的指向顺序，就是Morris遍历的顺序。 * 2）Morris遍历的过程中，存在寻找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) * 3）cur为空时遍历停止 * 示例： * 如下面这个二叉树： * ............a * ........../...\ * .........b.....c * ......../.\.../.\ * .......d..e..f...g * Morris遍历的顺序为：a -> b -> d -> b -> e -> a -> c -> f -> c -> g */publicstaticvoidmorris(Nodehead){if(head==null){return;}// cur 指针，指向当前访问的节点，初始为头节点Nodecur=head;// mostRight 指针,指向左子树最右侧的节点，初始为nullNodemostRight=null;// 开始遍历，对应过程的：3）cur为空时遍历停止while(cur!=null){// 先将mostRight指针指向当前节点的左孩子，这样就可以根据mostRight是否为空，判断是否有左孩子mostRight=cur.left;if(mostRight!=null){// 有左孩子，这个节点会被访问2次 ，// 依据过程 2）如果cur有左孩子，找到左子树上最右的节点mostRight// 找到左子树的最右侧节点，没有右子树或者上一次改成了指向自己，都要停止while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){// 第一次到达左子树的最右侧节点，对应过程2.1）mostRight.right=cur;cur=cur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点，对应过程2.2）mostRight.right=null;}}// else{// // 没有左孩子，这个节点会被访问1次，如果要单独挑出被访问一次的节点，可以加上else在这里判断// }// 对于过程 1）和2.2），即没有左孩子或者第二次访问节点，都会执行到这里，接下来访问当前节点的右孩子cur=cur.right;}}/** * Morris遍历实现前序遍历 * 思路： * cur第一次到达该节点时就访问，顺序为：根节点 -> 左子树 -> 右子树 * 因为Morris遍历的过程中，有左子树的节点会被访问两次，没有的会被访问1次， * 所以要挑出第一次访问的时候，就有两个地方： * 1） 对于有左子树的节点，第一次访问是根据mostRight的right指针为空的时候， * 2） 对于没有左子树的节点，第一次访问是根据cur的左孩子为空的时候， */publicstaticvoidmorrisPre(Nodehead){if(head==null){return;}System.out.print("morrisPre: ");Nodecur=head;NodemostRight=null;while(cur!=null){mostRight=cur.left;if(mostRight!=null){// 有左子树while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){// 第一次到达左子树的最右侧节点，对应过程2.1）System.out.print(cur.value+" ");mostRight.right=cur;cur=cur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点，对应过程2.2）mostRight.right=null;}}else{// 没有左子树，第一次访问是根据cur的左孩子为空的时候，System.out.print(cur.value+" ");}cur=cur.right;}System.out.println();}/** * Morris遍历实现中序遍历 * 思路： * cur第二次到达该节点时（即从左子树返回时）才访问，顺序为：左子树 -> 根节点 -> 右子树 * 因为Morris遍历的过程中，有左子树的节点会被访问两次，没有的会被访问1次， * 对于只访问一次的节点，就是直接访问了，对于访问两次的节点，是要在第二次访问， * 根据Morris的遍历代码可以看出，无论是没有左树还是第二次访问，都会走到最后指向右节点的位置， * 所以我们只需要在指向右节点之前访问信息就可以了。 */publicstaticvoidmorrisIn(Nodehead){if(head==null){return;}System.out.print("morrisIn : ");Nodecur=head;NodemostRight=null;while(cur!=null){mostRight=cur.left;if(mostRight!=null){// 有左子树while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){// 第一次到达左子树的最右侧节点，对应过程2.1）mostRight.right=cur;cur=cur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点，对应过程2.2）mostRight.right=null;}}// 没有左孩子和第二次到达，都会走到这里System.out.print(cur.value+" ");cur=cur.right;}System.out.println();}/** * Morris遍历实现后序遍历 * 思路： * cur第二次到达该节点时，逆序打印该节点左子树的右边界。最后，单独逆序打印整棵树的右边界， * 根据Morris遍历的过程，第二次到达该节点的位置很容易找到， * 麻烦的是如何逆序打印该节点左子树的右边界。 * 我们可以将左子树的有边界看成是一个链表，先用反转链表的方式将其转过来，然后打印，完成以后再反转回来。 */publicstaticvoidmorrisPos(Nodehead){if(head==null){return;}System.out.print("morrisPos: ");Nodecur=head;NodemostRight=null;while(cur!=null){mostRight=cur.left;if(mostRight!=null){// 有左子树while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){// 第一次到达左子树的最右侧节点，对应过程2.1）mostRight.right=cur;cur=cur.left;// 直接进行下一个 while循环continue;}else{// 第二次到达左子树的最右侧节点，对应过程2.2）mostRight.right=null;// 逆序打印左子树的有边界printEdge(cur.left);}}cur=cur.right;}// 单独打印整棵树的有边界printEdge(head);System.out.println();}/** * 逆序打印右边界 */publicstaticvoidprintEdge(Nodehead){// 先逆序右边界组成的链Nodetail=reverseEdge(head);// 此时打印，就是逆序的Nodecur=tail;while(cur!=null){System.out.print(cur.value+" ");cur=cur.right;}// 最后再逆序回来，恢复树的形状reverseEdge(tail);}/** * 逆序有边界组成的链 */publicstaticNodereverseEdge(Nodefrom){Nodepre=null;Nodenext=null;while(from!=null){next=from.right;from.right=pre;pre=from;from=next;}returnpre;}/** * Morris遍历判断是否为二叉搜索树 * 思路： * 二叉搜索树的左右子树都要比其父节点大， * 我们可以用中序遍历二叉树的方式，用一个变量记录上一个访问的节点的值， * 如果当前节点的值小于等于上一个节点的值，说明不是二叉搜索树。 */publicstaticbooleanisBST(Nodehead){if(head==null){returntrue;}Nodecur=head;NodemostRight=null;// 前一个访问的节点的值Integerpre=null;booleanans=true;while(cur!=null){mostRight=cur.left;if(mostRight!=null){while(mostRight.right!=null&&mostRight.right!=cur){mostRight=mostRight.right;}if(mostRight.right==null){mostRight.right=cur;cur=cur.left;continue;}else{mostRight.right=null;}}if(pre!=null&&pre>=cur.value){ans=false;}// 中序遍历的方式，所以只需要在这里改pre的值即可pre=cur.value;cur=cur.right;}returnans;}/** * 二叉树的节点定义 */publicstaticclassNode{publicintvalue;Nodeleft;Noderight;publicNode(intdata){this.value=data;}}publicstaticvoidmain(String[]args){Nodehead=newNode(4);head.left=newNode(2);head.right=newNode(6);head.left.left=newNode(1);head.left.right=newNode(3);head.right.left=newNode(5);head.right.right=newNode(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(head==null){return;}printInOrder(head.right,height+1,"v",len);Stringval=to+head.value+to;intlenM=val.length();intlenL=(len-lenM)/2;intlenR=len-lenM-lenL;val=getSpace(lenL)+val+getSpace(lenR);System.out.println(getSpace(height*len)+val);printInOrder(head.left,height+1,"^",len);}publicstaticStringgetSpace(intnum){Stringspace=" ";StringBufferbuf=newStringBuffer("");for(inti=0;i<num;i++){buf.append(space);}returnbuf.toString();}}

3、题目：求二叉树的最小深度

  • 题目：求二叉树的最小深度
  • 给定一个二叉树，找出其最小深度。
  • 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
  • 说明：叶子节点是指没有子节点的节点。
  • 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree

3.1、二叉树的递归套路实现方法

  • 二叉树的递归套路实现方法
  • 思路：
    • 根据二叉树的递归套路，我们需要最小的深度，那就要像左右节点要他们各自最小的深度，
    • 要到以后，取他们最小的深度，再加上1，就是以x为头的树的最小深度
    • 提交时方法名改为：minDepth
/** * 二叉树的递归套路实现方法 * 思路： * 根据二叉树的递归套路，我们需要最小的深度，那就要像左右节点要他们各自最小的深度， * 要到以后，取他们最小的深度，再加上1，就是以x为头的树的最小深度 * 提交时方法名改为：minDepth */publicstaticintminDepth(TreeNodehead){if(head==null){return0;}returnminDepthProcess(head);}/** * 递归函数的定义：返回x为头的树，最小深度是多少 */publicstaticintminDepthProcess(TreeNodex){if(x.left==null&&x.right==null){// 叶节点，返回1return1;}// 左右子树起码有一个不为空intleftH=Integer.MAX_VALUE;if(x.left!=null){leftH=minDepthProcess(x.left);}intrightH=Integer.MAX_VALUE;if(x.right!=null){rightH=minDepthProcess(x.right);}return1+Math.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(head==null){return0;}TreeNodecur=head;TreeNodemostRight=null;// 记录当前节点的深度的变量intcurLevel=0;// 记录最小高度的变量intminHeight=Integer.MAX_VALUE;while(cur!=null){mostRight=cur.left;if(mostRight!=null){// 统计到左子树最右边节点的距离intrightBoardSize=1;while(mostRight.right!=null&&mostRight.right!=cur){rightBoardSize++;mostRight=mostRight.right;}if(mostRight.right==null){// 第一次到达，深度加1curLevel++;mostRight.right=cur;cur=cur.left;continue;}else{// 第二次到达,此时的深度还没有减去右子树的深度，所以是子树最右侧节点的深度，需要统计到整体的里面if(mostRight.left==null){minHeight=Math.min(minHeight,curLevel);}// 减去右子树的深度，还原到当前节点的深度curLevel-=rightBoardSize;mostRight.right=null;}}else{// 只有一次到达的节点，直接统计深度，深度加1curLevel++;}cur=cur.right;}// 单独统计整棵树的最右边的深度intfinalRight=1;cur=head;while(cur.right!=null){finalRight++;cur=cur.right;}// 整个树的最右节点是一个叶子节点的时候，需要将最优节点的高度加进去，// 如果不是叶子节点，说明有左节点，肯定比finalRight大。所以不能把finalRight加进去。if(cur.left==null&&cur.right==null){minHeight=Math.min(minHeight,finalRight);}returnminHeight;}

后记
个人学习总结笔记，不能保证非常详细，轻喷

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！