問題 Leetcode 104. Maximum Depth of Binary Tree
バイナリ ツリーのルートを指定すると、その最大の深さを返します。
バイナリ ツリーの最大の深さは、ルート ノードから最も遠いリーフ ノードまでの最長パスに沿ったノードの数です。
Input: root = [3,9,20,null,null,15,7]
Output: 3
再帰
コード
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
int left=0, right = 0;
if(root == null) return 0;
left = 1 + maxDepth(root.left);
right = 1 + maxDepth(root.right);
return Math.max(left, right);
}
}
実行時間：0ms
メモリー：43.00MB
挙動
①現在地：3
maxDepth(root.left)により、次のrootに移動
②現在地:9
maxDepth(root.left)により、次のrootに移動。
③現在地：null
移動先がnullのため、0を返す。
④現在地：9
0が返されたため、1+0になり、変数leftに1を格納する。
次にmaxDepth(root.right)が動き、次のrootに移動。
⑤現在地：null
このrootもnullなので、0を返す。
⑥現在地：9
0が返されたため、1+0になり、変数rightに1を格納する。
leftとrightどちらも1のため、Math.maxでは1になり、1を返す。
⑦現在地：3
maxDepth(root.left)の戻り値は1になり、1+1で変数leftに2を格納する
次にmaxDepth(root.right)が動き、次のrootに移動する。
⑧現在地：20
maxDepth(root.left)により、次のrootに移動する
⑨現在地：15
maxDepth(root.left)により、次のrootに移動する。
⑩現在地：null
rootがnullのため、0を返す。
⑪現在地：15
0で返されたため、1+0になり、変数leftに1を格納する
maxDepth(root.right)により、次のrootに移動する。
⑫現在地：null
rootがnullのため、0を返す。
⑬現在地：15
0で返されたため、1+0になり、変数rightに1を格納する
leftとrightは共に1のため、1を返す。
⑭現在地：20
1で返されたため、1+1により変数leftに1を格納する
次にmaxDepth(root.right)を動かし、次のrootに移動する
⑮現在地：7
maxDepth(root.left)により、次のrootに移動する。
⑯現在地：null
rootがnullのため、0を返す。
⑰現在地：7
0で返されたため、1+0になり、変数leftに1を格納する
maxDepth(root.right)により、次のrootに移動する。
⑯現在地：null
rootがnullのため、0を返す。
⑰現在地：7
0で返されたため、1+0により変数rightに1を格納する
leftとrightは共に1のため、1を返す。
⑱現在地：20
1を返されたため、1+1により、変数rightに2を格納する
leftとrightは共に2のため、2を返す。
⑲現在地:3
maxDepth(root.right)の戻り値は2のため、1+2になり、変数rightに3を格納する。
変数leftは2、変数rightは3のため、3を返す。