[AlphaGo Study] [LeetCode] [JAVA] 104. Maximum Depth of Binary Tree

 

문제 설명

 Given a binary tree, find its maximum depth.

 The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

제한 사항

A leaf is a node with no children.

입출력 예

Binary tree	result
[3, 9, 20, null, null, 15, 7]	3

입출력 예 설명

#예제

Given binary tree [3, 9, 20, null, null, 15, 7]. Return its depth = 3.

 

leetcode.com/problems/maximum-depth-of-binary-tree/

Maximum Depth of Binary Tree - LeetCode

---

문제를 풀기 전 THINK

• 왼쪽 서브트리의 높이(leftDepth)와 오른쪽 서브트리의 높이(rightDepth)를 구하기 위하여, 순환 함수를 이용하여 각 서브트리의 끝까지 방문할 수 있도록 한다.
• 방문 순서는 leftDepth(root.left) 호출이 먼저 이루어졌기 때문에 왼쪽 먼저 끝까지 간다. 그 후 오른쪽 끝까지 방문한다.
• 이 때, 단말 노드를 만났을 때 순환이 끝나게 된다.
• 마지막에 +1을 해주는 이유는 트리 끝까지 내려가 있을 때, 한 단계 더 내려가서 살펴보려고 했는데 root == null 인 상황이 되었다. 이 때, 자식이 없으므로 leftDepth, rightDepth는 둘 다 0이 된다. ⇒ 내 자식들은 존재하지 않지만, 나는 존재한다! 따라서 "나"는 높이를 구할 때 하나의 수치로 환산될 수 있다.

   * 단말 노드란? 자식이 없는 노드.

     → 자식 노드가 있나 살펴보러 내려갔는데 아무 것도 없을 때, root == null 을 사용하여 순환을 끝낸다.

     → 자식 노드가 없으면 return 0을 한다.

나의 Solution

public class MaximumDepthBinaryTree {
	int maxDepth(TreeNode root) {
		int leftDepth, rightDepth;
		
		if(root == null) {
			return 0;
		} else {
			leftDepth = maxDepth(root.left);
			rightDepth = maxDepth(root.right);
			
			int resultDepth = Math.max(leftDepth, rightDepth);
			
			// 자식들이 존재하지 않아도 나는 존재할 수 있으니 +1
			return resultDepth + 1;
		}
	}
}