111. Minimum Depth of Binary Tree
이진 트리가 주어졌을 때, 최소 깊이를 구하세요. 최소 깊이는 루트 노드에서 가장 가까운 리프 노드까지 최단 경로를 따라 있는 노드의 개수입니다.
참고: 리프 노드는 자식 노드가 없는 노드입니다.
제약사항
- node의 개수는 [0, 10^5]
- -1000 <= Node.val <= 1000
아이디어
dfs로 트리를 순회하여 왼쪽 트리의 최솟값과 오른쪽 트리의 최솟값을 비교해서 최솟값 + 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 {
public int dfs(TreeNode node){
if(node == null){
return Integer.MAX_VALUE;
}
if (node.left == null && node.right == null){
return 1;
}
int left = dfs(node.left);
int right = dfs(node.right);
return Math.min(left, right) + 1;
}
public int minDepth(TreeNode root) {
if (root == null) return 0;
return dfs(root);
}
}1026. Maximum Difference Between Node and Ancestor
이진 트리의 루트가 주어졌을 때, v = |a.val - b.val|이고 a가 b의 조상인 서로 다른 노드 a와 b가 존재할 때의 최대값 v를 구하세요.
노드 a가 b의 조상인 경우는 다음 중 하나입니다. a의 자식 노드가 b와 같거나 a의 자식 노드가 b의 조상입니다.
제약사항
- 트리 노드의 개수는 [2, 5000]
- 0 <= Node.val <= 10^5
아이디어
1. 부모 리스트와 본인의 최대 v를 구한다.
2. max를 전역으로 두어서 업데이트한다.
/**
* 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 {
private int max = Integer.MIN_VALUE;
public void dfs(TreeNode node, List<TreeNode> ancestors){
if(node == null){
return;
}
int v = Integer.MIN_VALUE;
for(TreeNode ancestor : ancestors){
v = Math.max(v, Math.abs(node.val - ancestor.val));
}
max = Math.max(max, v);
ancestors.add(node);
dfs(node.left, ancestors);
dfs(node.right, ancestors);
ancestors.remove(node);
}
public int maxAncestorDiff(TreeNode root) {
dfs(root, new ArrayList<>());
return max;
}
}다른 방법도 찾아보자,,!
이진 트리의 루트가 주어졌을 때, 트리의 지름의 길이를 반환합니다. 이진 트리의 지름은 트리의 두 노드 사이의 가장 긴 경로의 길이입니다. 이 경로는 루트를 통과할 수도 있고 통과하지 않을 수도 있습니다. 두 노드 사이의 경로 길이는 두 노드 사이의 edge 수로 표현됩니다.
제약사항
- 트리 내 노드 개수는 [1, 10^4]
- -100 <= Node.val <= 100
아이디어
왼쪽 트리의 최대 깊이 + 오른쪽 트리의 최대 깊이
/**
* 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 {
private int maxDiameter = 0;
private int dfs(TreeNode node){
if (node == null){
return 0;
}
int left = dfs(node.left);
int right = dfs(node.right);
maxDiameter = Math.max(maxDiameter, left + right);
return Math.max(left, right) + 1;
}
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return maxDiameter;
}
}이진 트리의 루트가 주어지면 가장 깊은 리프 값의 합을 반환합니다.
제약사항
- 트리 내 노드 개수는 [1, 10^4]
- 1 <= Node.val <= 100
아이디어
가장 마지막 레벨의 노드 값의 합을 구해야한다.
/**
* 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 deepestLeavesSum(TreeNode root) {
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
int sum = 0;
while(!q.isEmpty()){
int size = q.size();
sum = 0;
for(int i = 0; i < size; i++){
TreeNode node = q.remove();
sum += node.val;
if(node.left != null) q.add(node.left);
if(node.right != null) q.add(node.right);
}
}
return sum;
}
}103. Binary Tree Zigzag Level Order Traversal
이진 트리의 루트가 주어지면, 해당 노드 값의 지그재그 수준 순서 탐색을 반환합니다. (즉, 왼쪽에서 오른쪽으로, 그 다음 수준에서는 오른쪽에서 왼쪽으로, 그리고 그 둘을 번갈아 탐색합니다).
제약사항
- 트리 내 노드 개수는 [0, 2000]
- -100 <= Node.val <= 100
아이디어
Level별 처리 -> BFS
/**
* 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null){
return new ArrayList<>();
}
List<List<Integer>> ans = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
boolean isLeftFirst = true;
while(!q.isEmpty()){
int size = q.size();
List<Integer> temp = new LinkedList<>();
for(int i = 0; i < size; i++){
TreeNode node = q.remove();
if (isLeftFirst) {
temp.addLast(node.val);
} else {
temp.addFirst(node.val);
}
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
ans.add(temp);
isLeftFirst = !isLeftFirst;
}
return ans;
}
}701. Insert into a Binary Search Tree
이진 탐색 트리(BST)의 루트 노드와 트리에 삽입할 값(value)이 주어졌습니다. 삽입 후 BST의 루트 노드를 반환합니다. 새 값은 원래 BST에 존재하지 않음이 보장됩니다. 삽입 후 트리가 BST로 유지되는 한, 삽입에 대한 여러 가지 유효한 방법이 있을 수 있습니다. 어떤 방법이든 반환할 수 있습니다.
삽입 후 트리가 BST로 유지되는 한, 삽입에 유효한 여러 가지 방법이 있을 수 있습니다. 어떤 방법이든 반환할 수 있습니다.
제약조건
- 트리 내 노드의 개수는 [0, 10^4]
- -10^8 <= Node.val <= 10^8
- Node.val는 유니크하다.
- -10^8 <= val <= 10^8
- val는 기존 BST에 존재하지 않습니다.
아이디어
재귀를 통해 BST 삽입
종료조건: null이면 내 자리
/**
* 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 TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
}