The title

img01

!!!!! The most recent common ancestor of binary trees – ligand

Analysis of the

First of all, for the problem of trees, the first thing is to think of recursion. Let the node being traversed be current, then the relationship between current and P and Q can be nothing more than the following:

  • P and Q are on the left side of current
  • P and Q are on the right side of current
  • P and Q are on both sides of current

For the first two cases, it’s easy to look in the opposite direction, but for the third case, it’s hard to determine what to look for, as shown below:

img02

In this case, we can see that p and Q are on the left and right of root, so we can traverse the two subtrees by left and right: if p or Q is not found, the subtrees are discarded. In this way, you can constantly narrow the search scope until you finally find the nearest common ancestor of the two nodes.

The specific code is as follows:

var lowestCommonAncestor = function (root, p, q) {

  if (root === null || root === p || root === q) return root;

  let left = lowestCommonAncestor(root.left, p, q);

  let right = lowestCommonAncestor(root.right, p, q);

  if (left === null) return right;

  if (right === null) return left;

  return root;

};

Copy the code

The results are as follows:

img03

expand

img04

!!!!! The nearest common ancestor of binary search tree – likou

First of all, we need to know what is binary search tree: on the basis of binary tree, left < root < right, is called binary search tree.

!!!!! 💡tip: Note that all nodes in the left subtree are smaller than root, as are the nodes in the right subtree

As shown below:

img05

The above structure has a characteristic: when the order traversal, the result must be an increasing sequence.

With a general understanding of the characteristics of binary search trees, there is obviously a simpler way to find common ancestors:

  • When p and q are greater than current, search to the right
  • When p and q are both less than current, look left
  • Otherwise, the nearest common ancestor of both has been found

The specific code is as follows:

var lowestCommonAncestor = function (root, p, q) {

  if (p.val > root.val && q.val > root.val) {

    return lowestCommonAncestor(root.right, p, q);

  } else if (p.val < root.val && q.val < root.val) {

    return lowestCommonAncestor(root.left, p, q);

  } else {

    return root;

  }

};

Copy the code

It is worth noting that since there is no need to record state, this problem does not require data structures such as stacks or queues even when iterating:

var lowestCommonAncestor = function (root, p, q) {

    while (root) {

      if (p.val > root.val && q.val > root.val) {

        root = root.right;

      } else if (p.val < root.val && q.val < root.val) {

        root = root.left;

      } else {

        return root;

      }

    }

};

Copy the code

The results are as follows:

img06