The nearest common ancestor of the BST

275. Lowest Common Ancestor of a Binary Search Tree

  1. If the root node is equal to p or Q, then the root node is the nearest common ancestor of p and Q;
  2. If the value of the root node is between the values of P and Q, it indicates that P and Q are on the left and right subtrees respectively, and the root node is the nearest common ancestor of P and Q.
  3. If the value of the root node is greater than the value of p and q, it means that both P and Q are in the left subtree of the root node.
  4. If the value of the root node is less than the value of p and q, it means that both P and Q are in the right subtree of the root node. Let’s go to the right subtree of the root node.
var lowestCommonAncestor = function(root, p, q) {
    const max = Math.max(p.val,q.val), min = Math.min(p.val,q.val);
    let res = null;
    dfs(root);
    return res;

    function dfs(node) {
        if(res||! node)return;
        if (node.val===p.val) res = p;
        else if (node.val===q.val) res = q;
        else if (node.val>min&&node.val<max) res = node;
        else if (node.val>max) dfs(node.left);
        elsedfs(node.right); }};Copy the code

The nearest common ancestor of a binary tree

236. Lowest Common Ancestor of a Binary Tree.

Idea 1: Firstly, find the path from the root node to p and Q nodes through DFS. The front part of these two paths is their common ancestor node. Just find the last identical node.

var lowestCommonAncestor = function(root, p, q) {
    const path1 = [], path2 = [];
    getPath(root,p,path1);
    getPath(root,q,path2);
    let res = null;
    const min = Math.min(path1.length,path2.length);
    for (let i = 0; i < min; i++) {
      if (path1[i]===path2[i]) res = path1[i];
      else return res;
    }
    return res;

    function getPath(node, targetNode, path) {
      if(! node)return false;
      path.push(node);
      if (targetNode===node) return true;
      else {
        if (getPath(node.left,targetNode,path)) return true;
        if (getPath(node.right,targetNode,path)) return true;
        path.pop();
        return false; }}};Copy the code

If P and Q are on the left and right subtrees of a node, then the node is the nearest common ancestor of P and Q. If a node is equal to p or q, and its child tree has q or P, then the node is also the nearest common ancestor of p and Q. Therefore, we need to return whether the subtree contains P and Q in each DFS.

var lowestCommonAncestor = function(root, p, q) {
    let res = null;
    dfs(root);
    return res;

    function dfs(node) {
      // Return 2: the subtree has p and Q; Returns 1: the subtree has one of p and q; Returns 0: there is no P or Q in the subtree
      if(! node)return 0;
      if (res) return 2;
      let left = dfs(node.left);
      if (left===2) return 2;
      if (left===1&&(node===p||node===q)) {
        res = node;
        return 2;
      }
      let right = dfs(node.right);
      if (right===2) return 2;
      if (right===1&&(node===p||node===q)) {
        res = node;
        return 2;
      }
      if (left+right===2) {
        res = node;
        return 2;
      }
      return left+right+(node===p||node===q)?1:0; }};Copy the code

The nearest common ancestor of the deepest leaf node

Link: 1123. Lowest Common Ancestor of Deepest Leaves.

One way to think about it is to refer to idea 1 of problem 2, find all the paths from the root node to the deepest leaf node, and then find the last common ancestor node.

There is a better way: for a node, if its left and right subtrees are of equal height, it is the nearest common ancestor of the deepest leaf of its root node. Look at the code.

var lcaDeepestLeaves = function(root) {
  let res = null, maxDepth = 0;
  dfs(root,0);
  return res;

  function dfs(node,depth) {
    // Returns the deepest depth of the subtree
    if(! node)return depth;
    let d1 = dfs(node.left,depth+1), d2 = dfs(node.right,depth+1);
    if (d1===d2&&d1>=maxDepth) {
      res = node;
      maxDepth = d1;
    }
    return Math.max(d1,d2); }};Copy the code