二元樹的最小深度問題

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

更多

演演算法和資料結構筆記