source: https://leetcode.com/problems/closest-leaf-in-a-binary-tree/description/
Given the root of a binary tree where every node has a unique value and a target integer k, return the value of the nearest leaf node to the target k in the tree.
Nearest to a leaf means the least number of edges traveled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.
Example 1:
Input: root = [1,3,2], k = 1
Output: 2
Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.
Example 2:
Input: root = [1], k = 1
Output: 1
Explanation: The nearest leaf node is the root node itself.
Example 3:
Input: root = [1,2,3,4,null,null,null,5,null,6], k = 2
Output: 3
Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.
Constraints:
- The number of nodes in the tree is in the range [1, 1000].
- 1 <= Node.val <= 1000
- All the values of the tree are unique.
- There exist some node in the tree where Node.val == k.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int findClosestLeaf(TreeNode root, int k) { //to store a node and it's level Map<Integer, Integer> dist = new HashMap<>(); //to store the leaf nodes List<Integer> leafs = new ArrayList<>(); //perform bfs bfs(root, leafs, dist); int min = Integer.MAX_VALUE; int res = -1; //for each leaf node find out lowest common ancestor of k and the leaf node for(int leaf: leafs){ TreeNode lca = lca(root, leaf, k); int a = dist.get(lca.val); //calculate distance between a leaf node and k int d = Math.abs(a - dist.get(k)) + Math.abs(a - dist.get(leaf)); if(min > d){ min = d; res = leaf; } } return res; } private TreeNode lca(TreeNode node, int p, int q){ if(node==null) return null; if(node.val == p || node.val == q){ return node; } TreeNode left = lca(node.left, p, q); TreeNode right = lca(node.right, p, q); if(left != null && right !=null){ return node; } if(left!=null) return left; return right; } private void bfs(TreeNode root, List<Integer> leafs, Map<Integer, Integer> dist){ Queue<TreeNode> next = new ArrayDeque<>(); next.add(root); int level = 0; while(!next.isEmpty()){ int size = next.size(); for(int i=0;i<size;i++){ TreeNode t = next.poll(); dist.put(t.val, level); if(t.left==null && t.right==null){ leafs.add(t.val); } if(t.left!=null){ next.add(t.left); } if(t.right!=null){ next.add(t.right); } } level++; } } } |