二叉树的最小深度问题

作者: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;
  }

更多

算法和数据结构笔记