直播平台怎么搭建_企业管理系统代码_seo外包靠谱_百度推广电话客服24小时

Description

Given the root of a binary tree, return the lowest common ancestor (LCA) of two given nodes, p and q. If either node p or q does not exist in the tree, return null. All values of the nodes in the tree are unique.

According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a binary tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)”. 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], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5. A node can be a descendant of itself according to the definition of LCA.

Example 3:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 10
Output: null
Explanation: Node 10 does not exist in the tree, so return null.

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
-10^9 <= Node.val <= 10^9
All Node.val are unique.
p != q

Follow up: Can you find the LCA traversing the tree, without checking nodes existence?

Solution

Use level order traversal to build a ancestor hash map. Then start searching for p and q. The idea is: calculate the height difference first, then let the lower node go diff first, then both of the nodes start going up, when these 2 pointers meet, the node is our lowest common ancestor.

An optimized way to do so is: let both of the pointers a, b go, if one of the pointers reaches the root (let’s assume here pointer a reaches), then move it to the lower node which is the other node (because the higher one must reach to the root first), now the remaining steps between root and b is the height difference. So when b reaches the root, a has moved diff steps, now move b to where a original starts, then both of these pointers move together until they meet. The node they meet is our lowest common ancestor.

Time complexity: $o(n+\log n)=o(n)$
Space complexity: $o(n)$

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':ancestor = {root: None}queue = collections.deque([root])while queue:node = queue.popleft()if node.left:ancestor[node.left] = nodequeue.append(node.left)if node.right:ancestor[node.right] = nodequeue.append(node.right)if p not in ancestor or q not in ancestor:return Nonep_node, q_node = p, qwhile p_node != q_node:p_node = ancestor[p_node] if p_node != root else qq_node = ancestor[q_node] if q_node != root else preturn p_node