Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream

1. Topic description

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

The definition of the nearest common ancestor in Baidu encyclopedia is: “For the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep 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)

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

2.

We’re going to use the properties of binary search trees

If both p and Q are greater than node value, it means that P and Q are in the right subtree of node. If both p and Q are smaller than node value, it means that P and Q are in the left subtree of node. If P is smaller than Node value, and Q is larger than node value, it means that node is the fork of P and Q in the binary search tree, namely, the nearest common ancestor

/** * 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) { while(true){ if(root.val <= Math.max(p.val, q.val) && root.val >= Math.min(p.val, q.val)){ break; }else if(root.val > Math.max(p.val, q.val)){ root = root.left; }else{ root = root.right; } } return root; }}Copy the code

Complexity analysis

  • Time complexity: O(n), where n is the number of nodes in a given binary search tree. The analytical thinking is the same as method 1.
  • Space complexity: O(1).

Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream