Leetcode
2020.05.01 20:17
783. Minimum Distance Between BST Nodes
조회 수 768 추천 수 0 댓글 0
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:
- The size of the BST will be between 2 and
100
. - The BST is always valid, each node's value is an integer, and each node's value is different.
- 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/
-
720. Longest Word in Dictionary
-
225. Implement Stack using Queues
-
56. Merge Intervals
-
844. Backspace String Compare
-
222. Count Complete Tree Nodes
-
697. Degree of an Array
-
605. Can Place Flowers
-
724. Find Pivot Index
-
448. Find All Numbers Disappeared in an Array
-
628. Maximum Product of Three Numbers
-
532. K-diff Pairs in an Array
-
897. Increasing Order Search Tree
-
872. Leaf-Similar Trees
-
876. Middle of the Linked List
-
203. Remove Linked List Elements
-
997. Find the Town Judge
-
270. Closest Binary Search Tree Value
-
687. Longest Univalue Path
-
783. Minimum Distance Between BST Nodes
-
235. Lowest Common Ancestor of a Binary Search Tree