DailyChallenge

104.二分木の最大深さ

イージー20200728

説明

二分木が与えられたとき、その最大深さを求めなさい。

二分木の深さは、ルート・ノードから最も遠いリーフ・ノードまでの最長経路上のノードの数です。

説明: リーフノードとは、子を持たないノードのことです。

 
二分木が与えられたとき[3,9,20,null,null,15,7] 
 3
 / 
 9 20
 / 
 15 7
は最大深度3を返す。

Solution

二分木の場合、一般的には一次走査の方が簡単で、階層走査の方が難しいということになります。考え方を広げるために、両方の方法について書きます。

バイナリーツリーについては、このアドレスが体系的に説明しています -github.com/Le...

1. 前置走査

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
 int res = 0;
 public int maxDepth(TreeNode root) {
 int temp = 1;
 dfs(root, temp);
 return res;
 }
 void dfs(TreeNode root, int temp){
 if(root == null) return;
 res = Math.max(res, temp);
 dfs(root.left, temp + 1);
 dfs(root.right, temp + 1);
 }
}

1. 階層的走査

class Solution {
 public int maxDepth(TreeNode root) {
 int res = 0;
 if(root == null) return 0;
 // 階層的トラバーサル
 Queue<TreeNode> q = new LinkedList<>();
 q.offer(root);
 while(!q.isEmpty()){
 int size = q.size();
 res++;
 while(size > 0){
 size--;
 TreeNode node = q.poll();
 if(node.left != null) q.offer(node.left);
 if(node.right != null) q.offer(node.right);
 }
 }
 return res;
 }
}

"

TODO: 動的計画法のトピックス