526互联

[LeetCode] 1676. Lowest Common Ancestor of a Binary Tree IV

发布时间 2023-07-20 01:53:40作者: CNoodle

Given the root of a binary tree and an array of TreeNode objects nodes, return the lowest common ancestor (LCA) of all the nodes in nodes. All the nodes will exist in the tree, and all values of the tree's nodes are unique.

Extending the definition of LCA on Wikipedia: "The lowest common ancestor of n nodes p1, p2, ..., pn in a binary tree T is the lowest node that has every pi as a descendant (where we allow a node to be a descendant of itself) for every valid i". A descendant of a node x is a node y that is on the path from node x to some leaf node.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7]
Output: 2
Explanation: The lowest common ancestor of nodes 4 and 7 is node 2.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [1]
Output: 1
Explanation: The lowest common ancestor of a single node is the node itself.

Example 3:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [7,6,2,4]
Output: 5
Explanation: The lowest common ancestor of the nodes 7, 6, 2, and 4 is node 5.

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -109 <= Node.val <= 109
  • All Node.val are unique.
  • All nodes[i] will exist in the tree.
  • All nodes[i] are distinct.

二叉树的最近公共祖先 IV。

题意是给了一棵二叉树和一个 nodes 数组，nodes 中的元素都存在于二叉树中。请找出这些节点的最小公共祖先。

思路是后序遍历，详细参见代码注释。

时间O(n)

空间O(n)

Java实现

 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     TreeNode res = null;
12 
13     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
14         // 把nodes放入hashset，这样可以以O(1)时间快速判断是否存在
15         Set<Integer> set = new HashSet<>();
16         for (TreeNode node : nodes) {
17             set.add(node.val);
18         }
19         helper(root, set);
20         return res;
21     }
22 
23     private int helper(TreeNode root, Set<Integer> set) {
24         // 统计当前子树内有多少节点存在于hashset
25         int count = 0;
26         if (root == null) {
27             return 0;
28         }
29         if (set.contains(root.val)) {
30             count++;
31         }
32         int left = helper(root.left, set);
33         int right = helper(root.right, set);
34         count += left;
35         count += right;
36         // 如果当前子树上的所有结点在set中都找到了且res为空，则res就是当前这棵子树
37         if (count == set.size() && res == null) {
38             res = root;
39         }
40         // 后序遍历往父节点返回的是当前子树内找到的存在于hashset内的节点个数
41         return count;
42     }
43 }

 

LeetCode 题目总结