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);
	}
	}
	}

Leetcode | Tree algorithm | Medium level | 50+ tree algorithms to solve

 I like to work on the following tree algorithms on Leetcode.com. 

1. 1361
2. 2476
3. 663
4. 333
5. 1902
6. 331
7. 1993
8. 742
9. 1430

742 is my favorite. I wrote one solution here.