Here is the link.
C# | Avoid searching in O(N) height tree | Array.BinarySearch
781
0
24 minutes ago
Intuition
Approach
- Apply inorder traversal first, and then apply binary search C# Array.BinarySearch.
- BinarySearch - if not found, return negative value - bitwise complement - larger than the given value
Complexity
- Time complexity:
- Space complexity:
Code
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
/// <summary>
/// Nov. 8, 2023
/// Avoid unbalanced tree - O(N) - tree height is same as O(N), N total number of nodes in the tree
/// Save binary tree in a sorted array first, and then apply binary search.
///
/// </summary>
/// <param name="root"></param>
/// <param name="queries"></param>
/// <returns></returns>
public IList<IList<int>> ClosestNodes(TreeNode root, IList<int> queries)
{
var sorted = new List<int>();
applyInOrder(root, sorted);
var result = new List<IList<int>>();
if (root == null)
{
return result;
}
foreach (var number in queries)
{
var found = sorted.BinarySearch(number);
if (found > -1)
{
result.Add(new int[] { sorted[found], sorted[found] });
}
else
{
var index = ~found;
var smallestLarger = -1;
var largestSmaller = -1;
if (index < sorted.Count)
{
smallestLarger = sorted[index];
if (index > 0)
{
largestSmaller = sorted[index - 1];
}
}
else
{
largestSmaller = sorted[sorted.Count - 1];
}
result.Add(new int[]{largestSmaller, smallestLarger}.ToList());
}
}
return result;
}
private void applyInOrder(TreeNode root, IList<int> list)
{
if (root == null)
{
return;
}
applyInOrder(root.left, list);
list.Add(root.val);
applyInOrder(root.right, list);
}
}