Tuesday, September 12, 2023

Leetcode 742 | 742. Closest Leaf in a Binary Tree - practice with a test case

 Here is the link of gist on github.com. 

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _742_closest_leaf_in_a_binary_tree
{
class Program
{
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;
}
}
static void Main(string[] args)
{
var root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.left.left = new TreeNode(5);
root.left.left.left.left = new TreeNode(6);
var test = new Program();
var result = test.FindClosestLeaf(root, 2);
Debug.Assert(result == 3);
}
/// <summary>
/// study code
/// https://leetcode.com/problems/closest-leaf-in-a-binary-tree/solutions/3381047/c-bfs-on-graph-solution/
/// </summary>
/// <param name="root"></param>
/// <param name="k"></param>
/// <returns></returns>
public int FindClosestLeaf(TreeNode root, int k)
{
var adjMap = new Dictionary<int, List<int>>();
var leaves = new HashSet<int>();
buildGraph(root, null, adjMap, leaves);
var visited = new HashSet<int>();
var queue = new LinkedList<int>();
queue.AddFirst(k);
visited.Add(k);
while (queue.Any())
{
var node = queue.First.Value;
queue.RemoveFirst();
if (leaves.Contains(node))
{
// BFS - first leaf node found
return node;
}
foreach (var next in adjMap[node])
{
// unvisited node - next
if (visited.Add(next))
{
queue.AddLast(next);
}
}
}
return -1;
}
/// <summary>
/// Build an undirected graph based on the binary tree
/// All node's values are unique - so the value can be the key to lookup
/// </summary>
/// <param name="node"></param>
/// <param name="parent"></param>
/// <param name="adjDict"></param>
/// <param name="leaves"></param>
void buildGraph(TreeNode node, TreeNode parent, Dictionary<int, List<int>> adjDict, HashSet<int> leaves)
{
if (node == null)
{
return;
}
adjDict[node.val] = new List<int>();
if (parent != null)
{
// build two directions - parent <-> child
// one direction -> two directions -> undirected graph
adjDict[node.val].Add(parent.val);
adjDict[parent.val].Add(node.val);
}
if (node.left == null && node.right == null)
{
leaves.Add(node.val);
}
buildGraph(node.left, node, adjDict, leaves);
buildGraph(node.right, node, adjDict, leaves);
}
}
}

No comments:

Post a Comment