この記事の内容は、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 このツリーは空ではありません。
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));
}
以上がJava でバイナリ ツリーの最大の深さを見つける方法 (コード付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。