2096. Step-By-Step Directions From a Binary Tree Node to Another

Leetcode link

解题思路

本题给了我们一棵二叉树，以及一个起点与一个终点，要求我们得出从起点到终点的最短路线

最短路线是一个字符串，有三个字符代表三个方向：

• U：往父节点走
• L：往左边子节点走
• R：往右边子节点走

本题可以分成三个步骤来走：

1. 找到最近共同父节点 LCA(Lowest Common Ancestor)：详见代码中的 findLCA 方法
2. 从 LCA 出发，分别遍历到起点与终点的路径：详见代码中的 findPath 方法
3. 最后，我们将起点终点的路径拼起来，注意从起点到 LCA 的路径要全部替换成 U

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} startValue
 * @param {number} destValue
 * @return {string}
 */
var getDirections = function(root, startValue, destValue) {
    const lca = findLCA(root, startValue, destValue);
    let startPath = [];
    let destPath = [];
    findPath(lca, startValue, startPath);
    findPath(lca, destValue, destPath);

    return 'U'.repeat(startPath.length) + destPath.reverse().join('')
};

// LCA: Lowest Common Ancestor
const findLCA = (node, startValue, destValue) => {
    if(!node || node.val === startValue || node.val === destValue) {
        return node;
    }

    const left = findLCA(node.left, startValue, destValue);
    const right = findLCA(node.right, startValue, destValue);

    // 遍历到这里有两种可能：
    // 1. startValue 与 destValue 有一个共同的祖先节点，此时 left && right 会同时存在
    // 2. startValue 或 destValue 是另一方的祖先节点，此时只有作为祖先节点的节点才会被赋值
    if(left && right) {
        return node;
    } else {
        return left ? left : right;
    }
}

const findPath = (node, target, path) => {
    if(!node) {
        return false;
    }
    if(node.val === target) {
        return true;
    }

    if(findPath(node.left, target, path)) {
        path.push('L');
        return true;
    }

    if(findPath(node.right, target, path)) {
        path.push('R');
        return true;
    }

    return false;
}