참고
문제해설
NOTE
•
입력 값 ⇒ TreeNode
•
출력 값 ⇒ Tree의 Node값들 중에서 가장 차이가 적은 값
문제 로직고민
NOTE
/**
* 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;
* }
* }
*/
Java
복사
1.
각 노드의 차이가 최소값이 나올 수 있는 경우는 자식노드와 비교했을 때이다!
•
더 내려갈수록 차이가 더 커지기 때문
•
노드를 모두 순회하면서 각 자식과의 차이를 비교한다!
•
전체 노드 순회만 하면 되므로 간단한 DFS로 구현한다.
2.
다시 생각해보니 위의 방식으로는 풀리지 않는다.
•
BST의 제거에서 좌측 서브트리의 가장 최대값을 찾는방식에서 생각했다.
•
좌측 서브트리에서 가장 오른쪽 값을 꺼내야한다.
•
우측 서브트리에서 가장 왼쪽 값을 꺼내야한다.
작성코드
NOTE
class Solution {
int result = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
dfs(root);
return result;
}
public void dfs(TreeNode node){
if(node == null) return;
if(node.left != null) result = Math.min(result, Math.abs(leftMax(node.left) - node.val));
if(node.right != null) result = Math.min(result, Math.abs(rightMin(node.right) - node.val));
dfs(node.left);
dfs(node.right);
}
private int leftMax(TreeNode node){
if(node.right == null) return node.val;
return leftMax(node.right);
}
private int rightMin(TreeNode node){
if(node.left == null) return node.val;
return rightMin(node.left);
}
}
Java
복사
정답코드
NOTE
class Solution {
public int getMinimumDifference(TreeNode root) {
List<Integer> nums = new ArrayList<>();
inOrder(root, nums);
int min = Integer.MAX_VALUE;
for (int i = 1; i < nums.size(); i++) {
min = Math.min(min, nums.get(i) - nums.get(i - 1));
}
System.gc();
return min;
}
public void inOrder(TreeNode root, List<Integer> nums) {
if (root == null) return;
inOrder(root.left, nums);
nums.add(root.val);
inOrder(root.right, nums);
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
중위순회를 활용한 DFS를 사용했다.
•
왜 num, num-1의 경우를 찾는게 차이의 최소값을 찾는지 몰랐는데 중위순회를 하면 Tree의 요소가 오름차순으로 정렬된다!