[Leetcode 13/100] Minimum Absolute Difference in BST - Easy

문제 풀이 방식

BST의 정렬된 특성 + inorder 재귀 구현 이용

inorder은 left -> selft -> right로 트리를 방문하므로 inorder로 트리를 순회했을 때, 순차적으로 방문할 수 있다.

주의할 점

트리 순회방식인 preorder, inorder, postorder를 이해하자

preorder : slef -> left -> right로 루트가 가장 먼저 나온다

inorder : left -> selft -> right 가장 왼쪽 노드가 먼저 나온다. (BST일 경우 정렬된 결과 볼 수 있음)

postorder : left -> right -> root 루트가 가장 늦게 나온다.

소스코드

/**
 * 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 {
    // inorder : left -> self -> right 로 방문하면 순서대로 나온다.
    // BST의 특징은 노드를 기준으로 왼쪽은 작고 오른쪾은 크다.
    
    int min;
    int prev;
    boolean flag;
    public int getMinimumDifference(TreeNode root) {
        min = Integer.MAX_VALUE;
        inorder(root);
        return min;
    }
    
    public void inorder(TreeNode root){
        
        if(root == null) return;
        
        inorder(root.left);
        
        if(!flag){
            flag = true;
        } else {
            min = Math.min(min, root.val - prev));
        }
        prev = root.val;
        inorder(root.right);
        
    }
}