字节一面:给定一个二叉树, 找到该树中两个指定节点间的最短距离
sisterAn opened this issue · 7 comments
sisterAn commented
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
7777sea commented
先找出两个节点的最近公共祖先
分别求出两个节点到最近公共祖先的路径长度
求出两个节点的路径长度
求公共祖先
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 commented
解答:
求最近公共祖先节点,然后再求最近公共祖先节点到两个指定节点的路径,再求两个节点的路径之和
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 commented
if(left === null) return right if(right === null) return left return root
这里应该是
if(left===null){ return right } if(right===null){ return root }
syc666 commented
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 commented
我的字节一面也是这个题
sisterAn commented
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 commented
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;
}