1676. 二叉树的最近公共祖先 IV

Difficulty
Medium
Tags
二叉树
URL
https://leetcode.ca/all/1676.html
Star
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:
notion imagenotion image
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.
Example 4:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [0,1,2,3,4,5,6,7,8]
Output: 3
Explanation: The lowest common ancestor of all the nodes is the root node.
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.

法 1 信息传递 - 自下而上

思路
参考
🎱
236. 二叉树的最近公共祖先 本题是找一堆节点nodes 的公共祖先，但因为所有节点都在树中，所以只要当前的节点 在nodes 中，就不用再往下走了，可以直接return 当前节点。
然后再回到上一层判断 左右子树的情况。
题解
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List') -> 'TreeNode':
        # 基线条件
        if root is None:
            return
				# 如果当前节点是在nodes中的节点
        if root in nodes:
            return root
        left = self.lowestCommonAncestor(root.left, nodes)
        right = self.lowestCommonAncestor(root.right, nodes)

        if left and right:
            return root
        if left is None and right is None:
            return None
        if left is None:
            return right
        else:
            return left