[LeetCode] - Maximum Depth of Binary Tree

이진 트리의 최대 깊이를 구하는 문제

 

의사 코드

root가 null인 경우 depth를 반환
아니면 left 혹은 right를 넣어서 순회
left와 right의 최대 깊이를 구함
둘 중에 큰 수를 반환

1차 시도

/**
 * 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 {
    int maximumDepth = 0;
    
    public int maxDepth(TreeNode root, int maximumDepth) {
        Integer temp = null;

        try {
            temp = new Integer(root.val);   // null과의 비교를 위한 형변환
        } catch(NullPointerException e){}

        if(temp != null)
        {
            maximumDepth++;
            maxDepth(root.left, maximumDepth);
            maxDepth(root.right, maximumDepth);
        }
        return maximumDepth;
    }
}

Error
Line 7: error: method maxDepth in class Solution cannot be applied to given types; [in __Driver__.java]
      int ret = new Solution().maxDepth(param_1);
                              ^
  required: TreeNode,int
  found:    TreeNode
  reason: actual and formal argument lists differ in length

주어진 Method의 Parameter를 변경하면 안 되는거 같다.

class Solution {
    public int maxDepth(TreeNode root) {        
        return getMaxDepth(root, 0);
  }
    
    public int getMaxDepth(TreeNode root, int depth) {
        if(root == null) return depth;
        depth++;
        
        getMaxDepth(root.left, depth);
        getMaxDepth(root.right, depth);
        
        return depth;
    }
}
input [3,9,20,null,null,15,7]
answer 1
expected 3

3

9, 20

null, null, 15, 7

left의 9 다음에 있는 null에서 depth를 return해서 1이 나오는 것 같다.

-> 둘 다 끝까지 순회한 다음에 max값을 Return해야함

 

class Solution {
    public int maxDepth(TreeNode root) {        
        return getMaxDepth(root, 0);
  }
    
    public int getMaxDepth(TreeNode root, int depth) {
        if(root == null) return depth;
        depth++;
        
        int leftMax = getMaxDepth(root.left, depth);
        int rightMax =getMaxDepth(root.right, depth);
        return Math.max(leftMax, rightMax);
    }
}

Runtime: 0 ms
Memory Usage: 39.1 MB

---

다른 사람 코드

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