二叉树的最小深度问题

二叉树,最小,深度,问题 · 浏览次数 : 224

小编点评

**二叉树最小深度问题** **递归解决方案** ```python def minDepth(head): if not head: return 0 # 处理左树 left_depth = minDepth(head.left) # 处理右树 right_depth = minDepth(head.right) # 返回最小深度 return min(left_depth, right_depth) + 1 ``` **Morris 遍历解决方案** ```python def minDepth(head): if not head: return 0 # 存储最右节点的位置 most_right = None # 遍历二叉树 cur = head heights = [] while cur: most_right = cur.left if most_right: duplicate = 1 while most_right.right and most_right.right != cur: duplicate += 1 most_right = most_right.right if most_right.right: heights.append(cur.height + 1) cur = cur.left else: heights.append(cur.height) cur = cur.right # 返回最小深度 return min(heights[-1]) ``` **时间复杂度** **递归解决方案：O(N)** * 递归调用会递归地遍历二叉树，因此时间复杂度为 O(N)，其中 N 是树中的节点数量。 **Morris 遍历解决方案：O(N)** * Morris 遍历使用一个变量来记录最右节点的层次，时间复杂度为 O(N)。 * 对于每个节点，如果它的左树存在，则记录它的层次。 * 对于每个节点，如果它的右树存在且右树没有右子节点，则记录它的层次。 * 最终，返回最小的层次。

正文

二叉树的最小深度问题

作者：Grey

原文地址：

博客园：二叉树的最小深度问题

CSDN：二叉树的最小深度问题

题目描述

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

题目链接见：LeetCode 111. Minimum Depth of Binary Tree

本题可以用两种方法来解，第一种方法，使用二叉树的递归套路，第二种方法是 Morris 遍历。

二叉树的递归套路解法

相关介绍见:使用二叉树的递归套路来解决的问题

定义递归函数

int minDepth(TreeNode head)

递归含义表示：以 head 为头的二叉树的最小深度为多少。

接下来是 base case，

if (null == head) {
    return 0;
}

显而易见，空树的深度是0；

接下来是普遍情况：

如果 head 的左树为空，则最小深度就是右树的最小深度加1；

如果 head 的右树为空，则最小深度就是左树的最小深度加1；

如果 head 的左右树都不为空，则最小深度就是左右树深度更大的那个加1。

完整代码如下

  public static int minDepth(TreeNode head) {
    if (head == null) {
      return 0;
    }
    if (head.left == null) {
      return minDepth(head.right) + 1;
    }
    if (head.right == null) {
      return minDepth(head.left) + 1;
    }
    return Math.min(minDepth(head.left), minDepth(head.right)) + 1;
  }

这个解法的时间复杂度是O(N)；

如果递归栈算空间的话，整个算法空间复杂度就是递归栈的复杂度O(N)。

Morris 遍历解法

使用 Morris 遍历，可以实现空间复杂度达到O(1),时间复杂度保持O(N)，Morris算法的介绍见:Morris 遍历实现二叉树的遍历

本题如果要用Morris遍历，需要解决的第一个问题是Morris发现当前层？

即：假设上一个节点是 X，在第 8 层，下一个遍历的节点是 Y，如何判断 Y 在第几层？

结论是：如果Y左树的最右节点是 A（非 X ），Y 必定是第 9 层，如果 Y 左树的最右节点是 X，那 Y 在第 X 层数-Y 的左树的右节点的个数

需要解决的第二个问题是Morris发现叶节点？

结论是：每个结点第二次回到自己的时候，因为要恢复指针，在恢复后，看下是否是叶子节点, 最后要单独遍历一下左树的最右节点。

完整代码见

  public static int minDepth(TreeNode head) {
    if (head == null) {
      return 0;
    }
    TreeNode cur = head;
    TreeNode mostRight;
    int curHeight = 0;
    int min = Integer.MAX_VALUE;
    while (cur != null) {
      mostRight = cur.left;
      if (mostRight != null) {
        int duplicate = 1;
        while (mostRight.right != null && mostRight.right != cur) {
          duplicate++;
          mostRight = mostRight.right;
        }
        if (mostRight.right == null) {
          curHeight++;
          mostRight.right = cur;
          cur = cur.left;
          continue;
        } else {
          if (mostRight.left == null) {
            min = Math.min(min, curHeight);
          }
          curHeight -= duplicate;
          mostRight.right = null;
        }
      } else {
        curHeight++;
      }
      cur = cur.right;
    }
    int rightMostHeight = 1;
    TreeNode c = head;
    while (c.right != null) {
      rightMostHeight++;
      c = c.right;
    }
    if (c.left == null) {
      min = Math.min(min, rightMostHeight);
    }
    return min;
  }

类似问题

LeetCode 104. Maximum Depth of Binary Tree

算法和数据结构笔记