742. Closest Leaf in a Binary Tree

Leetcode742ClosestLeafInABinaryTree.cs

/**
 * 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 {
    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);                               
        }
}