Topic describes

Given a binary search tree, find the nearest common ancestor of the two specified nodes in the tree.

The definition of recent public ancestor in Baidu Encyclopedia is: “For two nodes P and Q of the root tree T, the recent public ancestor is expressed as a node X, where x is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).

For example, given the following binary search tree: root = [6,2,8,0,4,7,9, null, null, 3, 5)

img

Example 1:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 8 output: 6: node 2 and 8 of recent common ancestor is 6.Copy the code

Example 2:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 4 output: 2: recent common ancestor node 2, and 4 is 2, because recent common ancestor nodes can be according to the definition for the node itself.Copy the code

Description:

  • All nodes have unique values.
  • P and Q are different nodes and exist in the given binary search tree.

solution

Search from top to bottom and find the first node between [p, q]. It can be implemented iteratively or recursively.

Python3

Iterative method

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if p == q:
            return p
        while root:
            if root.val < p.val and root.val < q.val:
                root = root.right
            elif root.val > p.val and root.val > q.val:
                root = root.left
            else:
                return root
Copy the code

The recursive method

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        return root
Copy the code

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p == q) {
            return p;
        }
        while (root != null) {
            if (root.val < p.val && root.val < q.val) {
                root = root.right;
            } else if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else {
                return root;
            }
        }
        return null;
    }
}
Copy the code

JavaScript

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */ var LowestCommonAncestor = function (root, p, q) { root) return null; if (root.val < p.val && root.val < q.val) { return lowestCommonAncestor(root.right, p, q); } else if (root.val > p.val && root.val > q.val) { return lowestCommonAncestor(root.left, p, q); } return root; };Copy the code