The sword refers to Offer 68 - I. Nearest Common Ancestor of Binary Search Trees

The sword refers to Offer 68 - I. The nearest common ancestor of a binary search treehttps://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

In a binary search tree:

1. If the left subtree of any node is not empty, the value of all nodes on the left subtree is not greater than the value of its root node.

2. If the right subtree of any node is not empty, the value of all nodes in the right subtree is not less than the value of its root node.

3. The left and right subtrees of any node are also binary search trees.

ie any node, left

Ancestor definition: If node p is in the left (right) subtree of node node, or p=node, then node is said to be the ancestor of p.

Definition of the nearest common ancestor: Let node node be a common ancestor of nodes p, q, if its left child node node.left and right child node.right are not p,qcommon ancestor, then node is called the "nearest common ancestor".

According to the above definition, if node is the nearest common ancestor of p,q, it can only be one of the following:

1. p and q are in the subtree of node, and the different sides of the node are divided (that is, in the left and right subtrees respectively);
2. p = node, and q is on the left or the left of node.In the right subtree;
3. q = node, and p is in the left or right subtree of node;

This question gives two important conditions: ① the tree is a binary search tree, ② the values ​​of all nodes of the tree are unique.According to the above conditions, the subtree relationship between p, q and node can be easily judged, namely:

If node.val < p.val, then pp is in the right subtree of node;
If node.val > p.val, then pp is in the left subtree of node;
If node.val =p.val , then p and node point to the same node.

So starting from the root node, if p and q are in the left subtree of node, iterate (or search) the left subtree of node,

P and q are in the right subtree of node to iterate (or search) the right subtree of node,

Otherwise return node

Method 1: Iterate
Loop search: Jump out when the node node is empty;
When both p and q are in the right subtree of node, then traverse to node.right;
Otherwise, whenIf both p and q are in the left subtree of node, then traverse to node.left;
Otherwise, it means that the nearest common ancestor has been found, and jump out.
Return value: The nearest common ancestor node.

class Solution:def lowestCommonAncestor(self, root, p, q):while root:if root.val>p.val and root.val>q.val:root=root.leftelif root.val

class Solution:def lowestCommonAncestor(self, root, p, q):while root:if root.val>p.val and root.val>q.val:root=root.leftelif root.val

Method 2: Recursion
Recursion work:
When both p, q are in the right subtree of node, open recursion node.right and return;
otherwise, when both p and q are in the left subtree of noed, open recursion noed.left and return;

Termination condition: that is, none of the returned nodes node
Return value: The nearest common ancestor node.

class Solution:def lowestCommonAncestor(self, root, p, q):def dfs(root,p,q):if root.val > p.val and root.val > q.val:return dfs(root.left,p,q)if root.val < p.val and root.val < q.val:return dfs(root.right,p,q)return rootreturn dfs(root,p,q)class Solution:def lowestCommonAncestor(self, root, p, q):if root.val > p.val and root.val > q.val:return self.lowestCommonAncestor(root.left,p,q)if root.val < p.val and root.val < q.val:returnself.lowestCommonAncestor(root.right,p,q)return root