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

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

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

求公共祖先

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;
}

解答：

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

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
}

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

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
}

我的字节一面也是这个题

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
}

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;
}

Navigation Menu

Repository navigation

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

解答：

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

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

Description

Activity

7777sea commented on Jul 14, 2020

sisterAn commented on Jul 14, 2020

解答：

xcgs123 commented on Nov 23, 2020

syc666 commented on Dec 16, 2020

Hanfee commented on May 6, 2021

sisterAn commented on Apr 18, 2022

realgeoffrey commented on Nov 29, 2023

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions