【スナップアルゴリズム】111-ツリーの最小深さ

タイトル
ツリーに最小深さを指定します.
最小深度は、ルートノードから最近接リーフノードへの最短パス上のノード数です.
説明:リーフノードとは、サブノードがないノードを指します.
例:
与えられた二叉木[3,9,20,null,null,15,7]は、

    3
   / \
  9  20
    /  \
   15   7

最小深度2を返します.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
問題解
ツリーの定義
まず、ツリーノード構造TreeNodeを定義します.

// Definition for a binary tree node.
public class TreeNode {
     
  int val;
  TreeNode left;
  TreeNode right;

  TreeNode(int x) {
     
    val = x;
  }
}

方法1:再帰
アルゴリズム#アルゴリズム#
最も直接的な考え方は再帰である.
この問題を深さ優先探索で解決した.

class Solution {
     
  public int minDepth(TreeNode root) {
     
    if (root == null) {
     
      return 0;
    }

    if ((root.left == null) && (root.right == null)) {
     
      return 1;
    }

    int min_depth = Integer.MAX_VALUE;
    if (root.left != null) {
     
      min_depth = Math.min(minDepth(root.left), min_depth);
    }
    if (root.right != null) {
     
      min_depth = Math.min(minDepth(root.right), min_depth);
    }

    return min_depth + 1;
  }
}

複雑度分析
時間複雑度:各ノードに1回アクセスし,時間複雑度はO(N)O(N)O(N)であり,ここでN Nはノード個数である.空間複雑度:最悪の場合、ツリー全体が非平衡であり、例えば各ノードに子供が1人しかいない場合、再帰的にはN N N(ツリーの高さ)回呼び出されるため、スタックの空間オーバーヘッドはO(N)O(N)O(N)O(N)である.しかし、最良の場合、木は完全にバランスがとれており、高さはlog(N)log(N)log(N)log(N)だけであるため、この場合の空間複雑度はO(log(N))O(log(N))O(log(N))のみである.
方法2:深度優先探索反復
スタックを用いて,上記の解法における再帰を反復に変えることができる.
各ノードに対して,深さ優先探索のポリシーに従ってアクセスし,リーフノードにアクセスしたときに最小深さを更新することが考えられる.
ルートノードを含むスタックから始め,現在の深さは1である.
次に反復を開始します.現在のスタックトップ要素をポップアップし、その子供ノードをスタックに押し込みます.リーフノードに遭遇すると、最小深度が更新されます.

import javafx.util.Pair;
class Solution {
     
  public int minDepth(TreeNode root) {
     
    LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
    if (root == null) {
     
      return 0;
    }
    else {
     
      stack.add(new Pair(root, 1));
    }

    int min_depth = Integer.MAX_VALUE;
    while (!stack.isEmpty()) {
     
      Pair<TreeNode, Integer> current = stack.pollLast();
      root = current.getKey();
      int current_depth = current.getValue();
      if ((root.left == null) && (root.right == null)) {
     
        min_depth = Math.min(min_depth, current_depth);
      }
      if (root.left != null) {
     
        stack.add(new Pair(root.left, current_depth + 1));
      }
      if (root.right != null) {
     
        stack.add(new Pair(root.right, current_depth + 1));
      }
    }
    return min_depth;
  }
}

複雑度分析
時間複雑度:各ノードはちょうど1回アクセスされ,複雑度はO(N)O(N)O(N)である.空間複雑度:最悪の場合、スタックに木全体を保存します.この場合、空間複雑度はO(N)O(N)O(N)O(N)です.
方法3:幅優先検索反復
深度優先検索メソッドの欠点は、最小深度が見つかるように、すべてのノードにアクセスする必要があることです.従って複雑度はO(N)O(N)O(N)である.
最適化の方法は、幅優先検索を利用して、ツリーの階層に従って反復し、最初にアクセスした葉が最小深さのノードであるため、すべてのノードを遍歴しないようにします.

import javafx.util.Pair;
class Solution {
     
  public int minDepth(TreeNode root) {
     
    LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
    if (root == null) {
     
      return 0;
    }
    else {
     
      stack.add(new Pair(root, 1));
    }

    int current_depth = 0;
    while (!stack.isEmpty()) {
     
      Pair<TreeNode, Integer> current = stack.poll();
      root = current.getKey();
      current_depth = current.getValue();
      if ((root.left == null) && (root.right == null)) {
     
        break;
      }
      if (root.left != null) {
     
        stack.add(new Pair(root.left, current_depth + 1));
      }
      if (root.right != null) {
     
        stack.add(new Pair(root.right, current_depth + 1));
      }
    }
    return current_depth;
  }
}

複雑度分析
時間の複雑さ:最悪の場合、これはバランスツリーであり、ツリーの階層に従ってすべてのノードにアクセスし、最後のノードを除去する必要があります.このようにN／2 N／2 N／2個のノードにアクセスするので,複雑度はO(N)O(N)O(N)である.空間複雑度:時間複雑度と同様にO(N)O(N)O(N)である.
作者:LeetCodeリンク:https://leetcode-cn.com/problems/two-sum/solution/er-cha-shu-de-zui-xiao-shen-du-by-leetcode/出典:力扣(LeetCode)著作権は作者の所有.商业転載は作者に连络して授権を得て、非商业転載は出典を明記してください.
感想
104題を参考にして,階層遍歴反復を1回行った.
実行時間:2 ms、すべてのJavaコミットで17.00%のユーザーを破った
メモリ消費量:36.8 MB、すべてのJavaコミットで84.54%のユーザーを破った

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
     
    public int minDepth(TreeNode root) {
     
        int res = 0;
        if(root==null) return res;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        res++;
        TreeNode nextFirst = null;
        TreeNode temp = null;
        while(!queue.isEmpty()){
     
            temp = queue.poll();
            if(temp==nextFirst) {
     
                nextFirst=null;
                res++;
            }
            if(temp!=null){
     
                if(temp.left==null && temp.right==null) return res;
                queue.add(temp.left);
                if(nextFirst==null && temp.left!=null) nextFirst = temp.left;
                queue.add(temp.right);
                if(nextFirst==null && temp.right!=null) nextFirst = temp.right; 
            }
        }
        return res;
    }
}

そして再帰を試してみました.
実行時間:1 ms、すべてのJavaコミットで98.07%のユーザーを破った
メモリ消費量:36.6 MB、すべてのJavaコミットで92.70%のユーザーを破った

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
     
    public int minDepth(TreeNode root) {
     
        if (root == null) {
     
            return 0;
        } else if(root.left==null&&root.right==null){
     
            return 1;
        } else if(root.left==null){
     
            return minDepth(root.right)+1;
        } else if(root.right==null){
     
            return minDepth(root.left)+1;
        } else {
     
            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        }
    }
}