Leetcode: Closest Leaf in a Binary Tree
LeetCode in Tree Binary Closest
2023-09-11 14:14:07 时间
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 = 1 Diagram of binary tree: 1 / \ 3 2 Output: 2 (or 3) 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 Diagram of binary tree: 1 / \ 2 3 / 4 / 5 / 6 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. Note: root represents a binary tree with at least 1 node and at most 1000 nodes. Every node has a unique node.val in range [1, 1000]. There exists some node in the given binary tree for which node.val == k.
Tree -----> Graph
- First, preform DFS on root in order to find the node whose val = k, at the meantime use
HashMap
to keep record of all back edges from child to parent; - Then perform BFS on this node to find the closest leaf node.
Note only the nodes visited in DFS are put into the backedgeMap, the others don't. This is fine, cause only from KNode to root this path, we need to check backMap.
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 class Solution { 11 public int findClosestLeaf(TreeNode root, int k) { 12 HashMap<TreeNode, TreeNode> backMap = new HashMap<>(); // store all edges that trace node back to its parent 13 HashSet<TreeNode> visited = new HashSet<>(); // visited node in BFS 14 Queue<TreeNode> queue = new LinkedList<>(); // for BFS 15 16 TreeNode KNode = dfs(root, k, backMap); // DFS: search for node whoes val == k 17 18 queue.offer(KNode); 19 visited.add(KNode); 20 21 while (!queue.isEmpty()) { 22 TreeNode cur = queue.poll(); 23 if (cur.left == null && cur.right == null) { 24 return cur.val; 25 } 26 if (cur.left != null && visited.add(cur.left)) { 27 queue.offer(cur.left); 28 } 29 if (cur.right != null && visited.add(cur.right)) { 30 queue.offer(cur.right); 31 } 32 if (backMap.containsKey(cur) && visited.add(backMap.get(cur))) { 33 queue.offer(backMap.get(cur)); 34 } 35 } 36 37 return -1; 38 } 39 40 public TreeNode dfs(TreeNode cur, int k, HashMap<TreeNode, TreeNode> backMap) { 41 if (cur.val == k) { 42 return cur; 43 } 44 if (cur.left != null) { 45 TreeNode left = dfs(cur.left, k, backMap); 46 backMap.put(cur.left, cur); 47 if (left != null) return left; 48 } 49 if (cur.right != null) { 50 TreeNode right = dfs(cur.right, k, backMap); 51 backMap.put(cur.right, cur); 52 if (right != null) return right; 53 } 54 return null; 55 } 56 }
相关文章
- Leetcode: Ones and Zeroes
- Leetcode: Strobogrammatic Number
- Leetcode: Search in Rotated Sorted Array II
- Leetcode: Search in Rotated Sorted Array
- <LeetCode OJ> 189. Rotate Array
- [LeetCode] 1304. Find N Unique Integers Sum up to Zero 和为零的N个唯一整数
- [LeetCode] 1288. Remove Covered Intervals 删除被覆盖区间
- [LeetCode] 1209. Remove All Adjacent Duplicates in String II 移除字符串中所有相邻的重复字符之二
- [LeetCode] 1104. Path In Zigzag Labelled Binary Tree 之字形二叉树路径
- [LeetCode] 979. Distribute Coins in Binary Tree 在二叉树中分配硬币
- [LeetCode] 964. Least Operators to Express Number 表示数字的最少运算符
- [LeetCode] 863. All Nodes Distance K in Binary Tree 二叉树距离为K的所有结点
- [LeetCode] Binary Search 二分搜索法
- [LeetCode] Second Minimum Node In a Binary Tree 二叉树中第二小的结点
- [LeetCode] Average of Levels in Binary Tree 二叉树的层平均值
- [LeetCode] Longest Line of Consecutive One in Matrix 矩阵中最长的连续1
- [LeetCode] 302. Smallest Rectangle Enclosing Black Pixels 包含黑像素的最小矩阵
- [LeetCode] 53. Maximum Subarray 最大子数组
- [LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二
- [LeetCode] 112. Path Sum 二叉树的路径和