742. Closest Leaf in a Binary Tree
Problem:
这套题还挺有意义的,拓宽了做题思路。
Use DFS to convert binary tree to undirected graph, then use BFS to get the closest leaf.
Solution:
Check leaf node first before getting its neighbors. If there is only one node, get node from null would throw error.
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.Analysis:
这套题还挺有意义的,拓宽了做题思路。
Use DFS to convert binary tree to undirected graph, then use BFS to get the closest leaf.
Solution:
Check leaf node first before getting its neighbors. If there is only one node, get node from null would throw error.
class Solution { TreeNode startNode; public int findClosestLeaf(TreeNode root, int k) { Map<TreeNode, List<TreeNode>> graph = new HashMap<>(); Queue<TreeNode> queue = new LinkedList<>(); buildGraph(root, null, graph, k); queue.offer(startNode); Set<TreeNode> seen = new HashSet<>(); while (!queue.isEmpty()) { TreeNode cur = queue.poll(); if (cur.left == null && cur.right == null) return cur.val; for (TreeNode node: graph.get(cur)) { if (seen.add(node)) { queue.offer(node); } } } throw null; } private void buildGraph(TreeNode node, TreeNode parent, Map<TreeNode, List<TreeNode>> graph, int k) { if (node == null) return; if (parent != null) { graph.computeIfAbsent(parent, n -> new ArrayList<>()).add(node); graph.computeIfAbsent(node, n -> new ArrayList<>()).add(parent); } if (node.val == k) startNode = node; buildGraph(node.left, node, graph, k); buildGraph(node.right, node, graph, k); } }
评论
发表评论