LeetCode 1650 Lowest Common Ancestor of a Binary Tree III

LeetCode

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:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

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:

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

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [2, 105]. -109 <= Node.val <= 109
All Node.val are unique. p != q
* p and q exist in the tree.

题目大意：

求带父节点的树中的两个节点的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为所有父亲路径长