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