LeetCode 1650 Lowest Common Ancestor of a Binary Tree III

<div>

Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

<pre>class Node { public int val; public Node left; public Node right; public Node parent; } </pre>

According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a 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)."

Example 1:

<pre>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. </pre>

Example 2:

<pre>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 since a node can be a descendant of itself according to the LCA definition. </pre>

Example 3:

<pre>Input: root = [1,2], p = 1, q = 2 Output: 1 </pre>

Constraints:

The number of nodes in the tree is in the range [2, 10<sup>5</sup>].
-10<sup>9</sup> <= Node.val <= 10<sup>9</sup>
All Node.val are unique.
p != q
p and q exist in the tree.

</div>

题目大意：

求带父节点的树中的两个节点的LCA。节点值唯一，且两输入节点不同，且一定存在

解题思路：

N/A

解题步骤：

N/A

注意事项：

某一个节点的左右父节点存入set中，另一节点的每个父节点在set中找

Python代码：

def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
	parent_set = set()
	it = p
	while it:
		parent_set.add(it)
		it = it.parent
	it = q
	while it:
		if it in parent_set:
			return it
		it = it.parent
	return None

算法分析：

时间复杂度为O(n + m)，空间复杂度O(n)，n和m为所有父亲路径长