Java でバイナリ ツリーの最大の深さを見つける方法 (コード付き)

この記事の内容は、Java でバイナリ ツリーの深さを最大にする方法 (コード付き) です。必要な方は参考にしていただければ幸いです。

二分木が与えられた場合、その最大の深さを見つけます。

バイナリ ツリーの深さは、ルート ノードから最も遠いリーフ ノードまでの最長パス上のノードの数です。

#説明: リーフ ノードは、子ノードを持たないノードを指します。

例:
指定されたバイナリ ツリー [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7

最大深さ 3 を返します。

# この質問を通じてツリーの使い方をマスターしましょう

質問分析: バイナリ ツリーの深さを調べます;

バイナリ ツリーの基本概念の概要を参照してバイナリ ツリーをさらに理解することができます;

この問題を解決するために再帰的手法も使用します。ルート ノードが空ではない場合、左のサブツリーと右のサブツリーを再帰的に走査して、どちらのサブツリーに多くのレベルがあるかを確認し、最後にリーフ ノードに到達するまで走査します。ステートメントの技術的な実装を使用します:

return nleft > ? nleft 1 : nright 1; このバイナリを取得します。例: 3

/ \

9 20 / \ 15 7

1 このツリーは空ではありません。

2. このツリーの左側のサブツリーを再帰的に走査します。左側のサブツリーが空でない場合、左側のサブツリーと右側のサブツリーの両方が空の場合、0 が返されます。判定、0 == 0、このツリーの左側のサブツリーは 0 1 = 1 を返します。

3 このツリーの右側のサブツリーを再帰的に走査します。右側のサブツリーは空ではありません。右サブツリー ツリーの左サブツリーと右サブツリーは空ではありません。右サブツリーの左サブツリーと右サブツリーの右サブツリーを再帰的に走査します。右サブツリーの左サブツリーと右サブツリーは空です。 0 を返す、右のサブツリーの左のサブツリーと右のサブツリーは空である、0 を返す、判断を行う、0 == 0、このツリーの右のサブツリーの左のサブツリーと右のサブツリーは 0 を返す 1 = 1 、 1 == 1 と判断すると、このツリーの右のサブツリーは 1 1 = 2 を返します。

4 左のサブツリーと右のサブツリーを比較します。この場合、このツリーは 2 1 = 3 を返し、このツリーの深さ、つまりレイヤーの数は 3 になります。

実際、主なアイデアは、この方法は次のとおりです。このツリーの葉ノードについては、最終的に葉ノードがルート ノードまで遡って 1 だけマージされるまで再帰的走査が続く限り、結果は次のパス長になります。 1.

コード実装:

public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int val)
        {
            data = val;
        }
    }

    public int maxDepth(TreeNode root)
    {
        if (root == null)
            return 0;

        int nleft = maxDepth(root.left);
        int nright = maxDepth(root.right);

        return nleft > nright ? nleft + 1 : nright + 1;
    }

メイン関数:

public static void main(String[] args)
    {
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);
        p.left.left = null;
        p.left.right = null;
        p.right.left = new TreeNode(4);
        p.right.right = new TreeNode(5);

        Tree1 t = new Tree1();
        System.out.println(t.maxDepth(p));
    }

実行結果: 3

以上がJava でバイナリ ツリーの最大の深さを見つける方法 (コード付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。