Leetcode
2020.05.01 20:17

783. Minimum Distance Between BST Nodes

조회 수 728 추천 수 0 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example :

Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4
        /   \
      2      6
     / \    
    1   3  

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

Note:

  1. The size of the BST will be between 2 and 100.
  2. The BST is always valid, each node's value is an integer, and each node's value is different.
  3. This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDiffInBST(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        
        queue.offer(root);
        while(queue.size() > 0){
            int size = queue.size();
            for(int i=0; i<size; i++){
                TreeNode node = queue.poll();
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
                
                list.add(node.val);
            }
            
        }
        
        Collections.sort(list);
        
        int minDiff = Integer.MAX_VALUE;
        int prev = list.get(0);
        for(int i=1; i<list.size(); i++){
            int tmpDiff = Math.abs(prev - list.get(i));
            if(tmpDiff < minDiff){
                minDiff = tmpDiff;
            }
            prev = list.get(i);
        }
        
        return minDiff;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDiffInBST(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        
        traverseBST(root, list);
        
        int minDiff = Integer.MAX_VALUE;
        int prev = list.get(0);
        for(int i=1; i<list.size(); i++){
            int tmpDiff = Math.abs(prev - list.get(i));
            if(tmpDiff < minDiff){
                minDiff = tmpDiff;
            }
            prev = list.get(i);
        }
        
        return minDiff;
    }
    
    public void traverseBST(TreeNode node, List<Integer> list){
        if(node == null){
            return;
        }
        
        traverseBST(node.left, list);
        list.add(node.val);
        traverseBST(node.right, list);
    }
}

[문제] https://leetcode.com/problems/minimum-distance-between-bst-nodes/



?

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
77 Leetcode [todo] 687. Longest Univalue Path hooni 2020.05.01 211
76 Programmers team game secret hooni 2020.04.30 0
75 Programmers hashmap secret hooni 2020.04.30 0
74 Programmers fib secret hooni 2020.04.30 0
73 Leetcode 997. Find the Town Judge hooni 2020.05.02 718
72 Leetcode 994. Rotting Oranges file hooni 2020.04.14 177
71 Leetcode 993. Cousins in Binary Tree file hooni 2020.04.30 222
70 Leetcode 973. K Closest Points to Origin hooni 2020.04.15 172
69 Leetcode 946. Validate Stack Sequences hooni 2020.04.08 162
68 Leetcode 937. Reorder Data in Log Files hooni 2020.04.25 165
67 Leetcode 897. Increasing Order Search Tree hooni 2020.05.04 687
66 Leetcode 876. Middle of the Linked List hooni 2020.05.04 678
65 Leetcode 872. Leaf-Similar Trees file hooni 2020.05.04 679
64 Leetcode 852. Peak Index in a Mountain Array hooni 2020.04.28 165
63 Leetcode 844. Backspace String Compare hooni 2020.05.05 748
» Leetcode 783. Minimum Distance Between BST Nodes hooni 2020.05.01 728
61 Leetcode 763. Partition Labels hooni 2020.04.17 222
60 Leetcode 75. Sort Colors hooni 2020.04.14 155
59 Leetcode 731. My Calendar II hooni 2020.04.15 159
58 Leetcode 729. My Calendar I hooni 2020.04.15 151
Board Pagination Prev 1 2 3 4 Next
/ 4