LeetCode 235 Lowest Common Ancestor of a Binary Search Tree

LeetCode

<div>

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

<pre>Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6. </pre>

Example 2:

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

Example 3:

<pre>Input: root = [2,1], p = 2, q = 1 Output: 2 </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 will exist in the BST.

</div>

题目大意：

BST中求给定的两节点的最低共同父亲节点

解题思路：

三种情况，也是用DFS

解题步骤：

N/A

注意事项：

1. pq一定存在，所以有**三种情况： 1) p或q是root，另一是其子孙。 2) p，q分列root两边。 3) p，q在root的一边。跟LeetCode 236 Lowest Common Ancestor of a Binary Tree不同的是，
   第二种情况，不用递归即知道，因为这是BST。第一和第三种情况同
2. 第二种情况由于要比较p, q, root顺序，所以要令p, q有序，Line 4-5

Python代码：

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
	if not root:
		return None
	if p.val > q.val: # remember
		return self.lowestCommonAncestor(root, q, p)
	if p.val <= root.val <= q.val or p == root or q == root: # remember root is p or q
		return root
	if p.val < root.val and q.val < root.val:
		return self.lowestCommonAncestor(root.left, p, q)
	else:
		return self.lowestCommonAncestor(root.right, p, q)

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)