LeetCodeアルゴリズム問題-Maximum Depth of Binary Tree

これは悦楽書の164回目の更新で、166編目のオリジナルです
01問題と準備を見る
今日はLeetCodeアルゴリズム問題のEasyレベルの23番目の問題(順位問題番号104)について説明します.ツリーが与えられ、その最大深さが見つかります.最大深さはルートノードから最も遠いリーフノードまでの最長パス上のノード数です.リーフはサブノードのないノードです.
例えば、所与の二叉木[3,9,20,null,null,15,7]は、

    3
   / \
  9  20
     / \
    15  7

深さ=3を返します.
今回の解題で使用される開発ツールはeclipse,jdkで使用されるバージョンは1.8,環境はwin 7 64ビットシステム,Java言語で作成およびテストされる.
02第一の解法
最大深さはルートノードから最も遠いリーフノード経路に含まれるノード数であり,上の二叉木を例にとると,最長経路は3−>20−>15,3−>20−>7の2つであり,この2つの経路のノード数はいずれも3つであるため,最後にその深さは3であると結論した.
特殊な場合1:入力されたツリーが空の場合、ノードはなく、深さは0です.
特殊な場合2:ルートノードのみの場合、その深さは1であり、それ自体のノードは1つしかありません.
通常の状況:簡単なツリーの深さ計算過程を一歩一歩導いてみることができますが、上記のツリーを例に挙げてみましょう.
ルートノードから開始すると、ノード数は1です.ノードが1つしかないためです.
ルートノードのサブノードに入ると、このとき最も長いパスは9という左サブノードと20という右サブノードを計算する最も長いパスであり、明らかに9は葉ノードであり、自分のノードしかない.20は独自のサブノードを持ち,その場合には20からの最長経路を算出する必要がある.
20には左サブノード15,右サブノード7があり,この場合15と7の最長パスを計算し続ける必要があるが,15と7はいずれもリーフノードであるため,ノード数は1のみであり,さらに20ノード自体というルートノードに属するサブノードを加えると,20ノードの最長パスは2である.
同じ3本のノードである2つのサブノード9,20は,サブノード9の最長パス上のノード数が1,サブノード20の最長パス上のノード数が2となり,最大値をとると,さらにルートノード自身のノード数を加えると,1+2=3,3が最長パス上のノード数,すなわちこの二叉木の深さとなる.
ここまで分析すると,ルートノードから最も遠いリーフノードまでのノード数を計算するには,まずその左右のサブノードの最長経路を計算する必要があり,左右のサブノードの最長経路を計算するには,彼ら自身の下の左右のサブノードの最長経路を計算する必要があることが分かった.さらにその最大値を上へ求めます.

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return 1 + Math.max(left, right);
}

03第2の解法
再帰を使うことができる以上、遍歴の方法を使ってみることもできます.ルートノードから開始し、サブノードを上から下に巡回します.これに対して、キューが来ると、巡回するたびにサブノードが格納されます.サブノードの階層を巡回すると、すべてのサブノードが巡回するまで1が加算されます.

public int maxDepth2(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int depth = 0;
    Queue q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        Queue tem = new LinkedList<>();
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if (node.left != null) {
                tem.offer(node.left);
            }
            if (node.right != null) {
                tem.offer(node.right);
            }
        }
        q = tem;
        depth++;
    }
    return depth;
}

特に、内層whileループは、第1の解法と同様に、各層を巡るサブノードである.
04第3の解法
第2の解法の内層サイクルでは、新しいキューを使用して、サイクルごとに入る次の層ノードデータを受信します.変更して、より簡潔にすることができますか?ここではキューのサイズを使用して制御します.ルートノードから、キューに入った後、キューのsizeは1で、内層ループに入り始めます.内層ループが1回歩いた後、キューには2つのサブノードが追加されました.このときのsizeは2で、すべてのサブノードが遍歴するまで、内層ループを開始し続けます.

public int maxDepth3(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int depth = 0;
    Queue q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int n = q.size();
        while(n-- > 0){
            TreeNode node = q.poll();
            if (node.left != null) {
                q.offer(node.left);
            }
            if (node.right != null) {
                q.offer(node.right);
            }
        }
        depth++;
    }
    return depth;
}

05検証とテスト
上記の2つの解法について,簡単なツリーを用いてデータテストを行った.

public static void main(String[] args) {
    Easy_104_MaximumDepthOfBinaryTree instance = new Easy_104_MaximumDepthOfBinaryTree();
    TreeNode t = new TreeNode(1);
    TreeNode t2 = new TreeNode(2);
    TreeNode t3 = new TreeNode(3);
    TreeNode t4 = new TreeNode(4);
    TreeNode t5 = new TreeNode(5);
    TreeNode t6 = new TreeNode(6);
    TreeNode t7 = new TreeNode(7);
    TreeNode t8 = new TreeNode(8);
    t.left = t2;
    t.right = t3;
    t2.left = t4;
    t2.right = t5;
    t3.left = t6;
    t3.right = t7;
    t7.left = t8;
    long start = System.nanoTime();
    int result = instance.maxDepth(t);
    long end = System.nanoTime();
    System.out.println("maxDepth---  ："+result+" ,   ："+(end-start)/1000+"  ");
    long start2 = System.nanoTime();
    int result2 = instance.maxDepth2(t);
    long end2 = System.nanoTime();
    System.out.println("maxDepth2---  ："+result2+" ,   ："+(end2-start2)/1000+"  ");
    long start3 = System.nanoTime();
    int result3 = instance.maxDepth3(t);
    long end3 = System.nanoTime();
    System.out.println("maxDepth3---  ："+result3+" ,   ："+(end3-start3)/1000+"  ");
}

テスト結果は次のとおりです.

maxDepth---  ：4 ,   ：23  
maxDepth2---  ：4 ,   ：586  
maxDepth3---  ：4 ,   ：16  

テストの結果から、遍歴と再帰は問題を解決できることがわかります.2つ目の解法は、ループを進むたびに新しいオブジェクトを作成するため、メモリと実行時間の消費量が少なくないため、最適化された3つ目の解法が遍歴に適しています.
06小結
以上はすべての内容で、もしみんなが何か良い解法の構想、提案あるいはその他の問題があれば、下の伝言で交流することができて、いいね、伝言、転送は私に対する最大のリターンと支持です!