728x90
104 - Maximum Depth of Binary Tree


풀이
이진 트리 노드 정의 클래스
- `val`: 자기 값
- `left`: 왼쪽 자식
- `right`: 오른쪽 자식
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;
}
}
최대 깊이: 루트에서 가장 먼 리프 노드까지의 가장 긴 경로에 있는 노드의 개수
ex. root = [3, 9, 20, null, null, 15, 7]
-> 가장 긴 경로: 3 -> 20 -> 15 / 3 -> 20 -> 7 => 3개
현재 노드 깊이 = 1 + max(왼쪽 깊이, 오른쪽 깊이)
root가 null이면 깊이 0
코드
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int lt = maxDepth(root.left);
int rt = maxDepth(root.right);
return 1 + Math.max(lt, rt);
}
}
872 - Leaf-Similar Trees


풀이
List<Integer> leaves1 = new ArrayList<>();
List<Integer> leaves2 = new ArrayList<>();
dfs(root1, leaves1);
dfs(root2, leaves2);
두 트리에서 리프 노드만 왼쪽부터 순서대로 모아서 비교
리프(leaf): 자식이 없는 노드
node.left == null && node.right == null
코드
class Solution {
void dfs(TreeNode node, List<Integer> leaves) {
if (node == null) return;
if (node.left == null && node.right == null) {
leaves.add(node.val);
return;
}
dfs(node.left, leaves);
dfs(node.right, leaves);
}
public boolean leafSimilar(TreeNode root1, TreeNode root2) {
List<Integer> leaves1 = new ArrayList<>();
List<Integer> leaves2 = new ArrayList<>();
dfs(root1, leaves1);
dfs(root2, leaves2);
return leaves1.equals(leaves2);
}
}
1448 - Count Good Nodes in Binary Tree


풀이
good node: root -> x 경로에서 x보다 큰 값이 없어야 함
=> x >= 경로에서 최대값
-> 지금까지 경로에서 최대값 같이 전달해서 현재 노드 값과 비교, 최대값 갱신
코드
class Solution {
int dfs(TreeNode node, int max) {
if (node == null) return 0;
int cnt = 0;
if (node.val >= max) cnt = 1;
max = Math.max(max, node.val);
cnt += dfs(node.left, max);
cnt += dfs(node.right, max);
return cnt;
}
public int goodNodes(TreeNode root) {
return dfs(root, root.val);
}
}
출처
LeetCode 75 - Study Plan - LeetCode
Ace Coding Interview with 75 Qs
leetcode.com
728x90
반응형