Given a binary tree where every node has a unique value, and a target key k, find the value of the nearest leaf node to target k in the tree.

Here, nearest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.

In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.

Example 1:

Input:root = [1, 3, 2], k = 1Diagram of binary tree:          1         / \        3   2Output: 2 (or 3)Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.

 

Example 2:

Input:root = [1], k = 1Output: 1Explanation: The nearest leaf node is the root node itself.

 

Example 3:

Input:root = [1,2,3,4,null,null,null,5,null,6], k = 2Diagram of binary tree:             1            / \           2   3          /         4        /       5      /     6Output: 3Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.

 

Note:

1. root represents a binary tree with at least 1 node and at most 1000 nodes.
2. Every node has a unique node.val in range [1, 1000].
3. There exists some node in the given binary tree for which node.val == k.

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     public int val; 5  *     public TreeNode left; 6  *     public TreeNode right; 7  *     public TreeNode(int x) { val = x; } 8  * } 9  */10 public class Solution {11     public int FindClosestLeaf(TreeNode root, int k) {12         var leaves = new List
     
      ();13         FindAllLeaves(root, leaves);14         15         var lcas = new List
      
       ();16         foreach (var l in leaves)17         {18             lcas.Add(FindLCA(root, l.val, k));19         }20         21         TreeNode res = null;22         var min = Int32.MaxValue;23         24         for (int i = 0; i < lcas.Count; i++)25         {26             int cur = GetSteps(lcas[i], leaves[i].val) + GetSteps(lcas[i], k);27             if (cur < min)28             {29                 res = leaves[i];30                 min = cur;31             }32         }33         34         return res.val;35     }36     37     private void FindAllLeaves(TreeNode node, IList
       
         leaves)38     {39         if (node == null) return;40         if (node.left == null && node.right == null)41         {42             leaves.Add(node);43             return;44         }45         46         FindAllLeaves(node.left, leaves);47         FindAllLeaves(node.right, leaves);48     }49     50     private TreeNode FindLCA(TreeNode node, int a, int b)51     {52         if (node == null) return null;53         if (node.val == a || node.val == b) return node;54         55         var left = FindLCA(node.left, a, b);        56         var right = FindLCA(node.right, a, b);57         58         if (left != null && right != null)59         {60             return node;61         }62         else if (left != null)63         {64             return left;65         }66         else67         {68             return right;69         }70     }71     72     private int GetSteps(TreeNode parent, int k)73     {74         if (parent == null) return -1;75         if (parent.val == k) return 0;76         77         var left = GetSteps(parent.left, k);78         if (left != -1)79         {80             return left + 1;81         }82         83         var right = GetSteps(parent.right, k);84         return right == -1 ? -1 : right + 1;85     }86 }