字节一面：给定一个二叉树, 找到该树中两个指定节点间的最短距离

[sisterAn]

function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}

[7777sea]

先找出两个节点的最近公共祖先
分别求出两个节点到最近公共祖先的路径长度
求出两个节点的路径长度

求公共祖先

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 && right) {
        return root
    }
    return left || right
};

计算距离

let visited = false
let stack = []
var getDisToPar = function(root, p, stack) {
    if(root==null){
         return ;
     }
    //将节点添加到栈中
     stack.push(root.val);
    //如果找到了
    if(!visited&&root==p){
        visited  = true;
        return;
     }
    //先找左子树
    if(!visited){
        getDisToPar(root.left,p,stack);
    }
    //左子树没找到再找右子树
    if(!visited){
        getDisToPar(root.right,p,stack);
    }
    //如果还没找到，说明不在这个节点下面，弹出来
    if(!visited){
        stack.pop();
    }
    return;
}

[sisterAn]

解答：

求最近公共祖先节点，然后再求最近公共祖先节点到两个指定节点的路径，再求两个节点的路径之和

const shortestDistance = function(root, p, q) {
    // 最近公共祖先
    let lowestCA = lowestCommonAncestor(root, p, q)
    // 分别求出公共祖先到两个节点的路经
    let pDis = [], qDis = []
    getPath(lowestCA, p, pDis)
    getPath(lowestCA, q, qDis)
    // 返回路径之和
    return (pDis.length + qDis.length)
}

// 最近公共祖先
const lowestCommonAncestor = function(root, p, q) {
    if(root === null || root === p || root === q) return root
    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)
    if(left === null) return right
    if(right === null) return left
    return root
}

const getPath = function(root, p, paths) {
    // 找到节点，返回 true
    if(root === p) return true
    // 当前节点加入路径中
    paths.push(root)
    let hasFound = false
    // 先找左子树
    if (root.left !== null)
        hasFound = getPath(root.left, p, paths)
    // 左子树没有找到，再找右子树
    if (!hasFound && root.right !== null)
        hasFound = getPath(root.right, p, paths)
    // 没有找到，说明不在这个节点下面，则弹出
    if (!hasFound)
        paths.pop()
    return hasFound
}

[xcgs123]

if(left === null) return right if(right === null) return left return root
这里应该是
if(left===null){ return right } if(right===null){ return root }

[syc666]

function fn(root,node1,node2) {
  let res = 0
  const getParent = (root, node1, node2) => {
    if (!root || root === node1 || root === node2) return root
    const left = getParent(root.left, node1, node2)
    const right = getParent(root.right, node1, node2)
    if (!left) return right
    if (!right) return left
    return root
  }
  const getDis = (parent, child) => {
    if(!parent) return -1
    if (parent === child) return 0 
    const left = getDis(parent.left, child)
    const right = getDis(parent.right,child)
    
    if (left !== -1) return left+1
    if ( right!== -1) return right+1
    return -1
  }
  res = getDis(root, node1)
  res = getDis(root, node2)
  return res
}

[Hanfee]

我的字节一面也是这个题

[sisterAn]

var minDist = function(root, p, q) {
  let common = lowestCommonNode(root, p, q)
  if(!common) return Infinity
  let res = []
  let depth = function(node, sum) {
    if(!node || res.length === 2) return
    if(node === p || node === q) {
      res.push(sum)
    }
    depth(node.left, sum+node.val)
    depth(node.right, sum+node.val)
  }
  depth(root, 0)
  return res.reduce((acc, cur)=>acc+cur)
}

var lowestCommonNode = function(root, p, q) {
  if(root === null || p === root || q === root) {
    return root
  }
  let left = lowestCommonNode(root.left, p, q)
  let right = lowestCommonNode(root.right, p, q)
  if(left && right) {
    return root
  }
  return left || right
}

[realgeoffrey]

var getDirections = function (root, startValue, destValue) {
  let pathToStart = [root];
  helper(root, startValue, pathToStart);

  let pathToDest = [root];
  helper(root, destValue, pathToDest);

  let commonParent = null;  // 最近公共祖先（若要求返回节点值）

  // 找到最近公共祖先
  while (
    pathToStart.length > 0 &&
    pathToDest.length > 0 &&
    pathToStart[0] === pathToDest[0]
  ) {
    commonParent = pathToStart[0];

    pathToStart = pathToStart.slice(1);
    pathToDest = pathToDest.slice(1);
  }

  // 若是 https://leetcode.cn/problems/step-by-step-directions-from-a-binary-tree-node-to-another/description/ ，则左边向上 + 右边向下
  // return "U".repeat(pathToStart.length) + pathToDest.join("");

  // 若要求返回节点值，则：
  // return pathToStart.reverse().concat(commonParent).concat(pathToDest).map((node)=>node.val);

  // 若要求返回长度，则：
  return pathToStart.length + 1 + pathToDest.length;
};

// 递归、深度优先，查找：以node为根节点，目标是target的路径，路径存储在path
function helper(node, target, path) {
  if (node === null) { return false; }

  if (node.val === target) { return true; }

  // 向左
  path.push("L" /* 若要求返回节点值，则：node.left */);
  if (helper(node.left, target, path)) { return true; }
  path.pop(); // 没找到，回溯

  // 向右
  path.push("R" /* 若要求返回节点值，则：node.right */);
  if (helper(node.right, target, path)) { return true; }
  path.pop(); // 没找到，回溯

  return false;
}