Medium

题目描述

给定一个有 n 个节点的二叉树的根节点 root，每个节点都有一个从 1 到 n 的唯一值。同时给定一个整数 startValue 表示起始节点 s 的值，以及一个不同的整数 destValue 表示目标节点 t 的值。

找到从节点 s 开始到节点 t 结束的最短路径。生成这种路径的逐步指令，作为一个只包含大写字母 ‘L’、‘R’ 和 ‘U’ 的字符串。每个字母表示一个特定的方向：

  • ‘L’ 表示从一个节点到它的左子节点。
  • ‘R’ 表示从一个节点到它的右子节点。
  • ‘U’ 表示从一个节点到它的父节点。

返回从节点 s 到节点 t 的最短路径的逐步指令。

示例 1：

输入：root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6
输出："UURL"
解释：最短路径是：3 → 1 → 5 → 2 → 6。

示例 2：

输入：root = [2,1], startValue = 2, destValue = 1
输出："L"
解释：最短路径是：2 → 1。

约束条件：

  • 树中节点的数量是 n
  • 2 <= n <= 10^5
  • 1 <= Node.val <= n
  • 树中所有值都是唯一的
  • 1 <= startValue, destValue <= n
  • startValue != destValue

解题思路

这道题的关键思路是利用二叉树中任意两个节点之间的最短路径必须经过它们的最近公共祖先（LCA）这一性质。

解题步骤：

  1. 找到根节点到起始节点和目标节点的路径：使用DFS分别找到从根节点到startValue和destValue的路径字符串，记录沿途的方向（‘L’或’R’）。

  2. 找到最近公共祖先（LCA）：比较两条路径，找到最长的公共前缀。去除公共前缀后，剩余部分就是从LCA到各自节点的路径。

  3. 构造最终路径：

    • 从起始节点到LCA：将从LCA到起始节点的路径反向，全部变成’U’（向上移动）
    • 从LCA到目标节点：直接使用从LCA到目标节点的路径

算法复杂度分析：

  • 时间复杂度：O(n)，其中n是树中节点的数量，需要遍历整棵树来找到路径
  • 空间复杂度：O(h)，其中h是树的高度，用于递归调用栈和路径字符串存储

这种方法避免了复杂的LCA算法，直接通过路径比较来实现，思路清晰且实现简单。

代码实现

class Solution {
public:
    string getDirections(TreeNode* root, int startValue, int destValue) {
        string startPath, destPath;
        
        // 找到从root到startValue和destValue的路径
        findPath(root, startValue, startPath);
        findPath(root, destValue, destPath);
        
        // 找到公共前缀的长度
        int commonLen = 0;
        while (commonLen < startPath.length() && commonLen < destPath.length() && 
               startPath[commonLen] == destPath[commonLen]) {
            commonLen++;
        }
        
        // 构造结果：从start到LCA全是'U'，然后加上从LCA到dest的路径
        string result = string(startPath.length() - commonLen, 'U') + 
                       destPath.substr(commonLen);
        
        return result;
    }
    
private:
    bool findPath(TreeNode* root, int target, string& path) {
        if (!root) return false;
        
        if (root->val == target) return true;
        
        // 尝试左子树
        path.push_back('L');
        if (findPath(root->left, target, path)) return true;
        path.pop_back();
        
        // 尝试右子树
        path.push_back('R');
        if (findPath(root->right, target, path)) return true;
        path.pop_back();
        
        return false;
    }
};

class Solution:
    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
        def find_path(node, target, path):
            if not node:
                return False
            
            if node.val == target:
                return True
            
            # 尝试左子树
            path.append('L')
            if find_path(node.left, target, path):
                return True
            path.pop()
            
            # 尝试右子树
            path.append('R')
            if find_path(node.right, target, path):
                return True
            path.pop()
            
            return False
        
        # 找到从root到startValue和destValue的路径
        start_path = []
        dest_path = []
        find_path(root, startValue, start_path)
        find_path(root, destValue, dest_path)
        
        # 找到公共前缀的长度
        common_len = 0
        while (common_len < len(start_path) and 
               common_len < len(dest_path) and 
               start_path[common_len] == dest_path[common_len]):
            common_len += 1
        
        # 构造结果
        return 'U' * (len(start_path) - common_len) + ''.join(dest_path[common_len:])

public class Solution {
    public string GetDirections(TreeNode root, int startValue, int destValue) {
        var startPath = new List<char>();
        var destPath = new List<char>();
        
        // 找到从root到startValue和destValue的路径
        FindPath(root, startValue, startPath);
        FindPath(root, destValue, destPath);
        
        // 找到公共前缀的长度
        int commonLen = 0;
        while (commonLen < startPath.Count && commonLen < destPath.Count && 
               startPath[commonLen] == destPath[commonLen]) {
            commonLen++;
        }
        
        // 构造结果
        var result = new StringBuilder();
        
        // 从start到LCA全是'U'
        for (int i = 0; i < startPath.Count - commonLen; i++) {
            result.Append('U');
        }
        
        // 加上从LCA到dest的路径
        for (int i = commonLen; i < destPath.Count; i++) {
            result.Append(destPath[i]);
        }
        
        return result.ToString();
    }
    
    private bool FindPath(TreeNode root, int target, List<char> path) {
        if (root == null) return false;
        
        if (root.val == target) return true;
        
        // 尝试左子树
        path.Add('L');
        if (FindPath(root.left, target, path)) return true;
        path.RemoveAt(path.Count - 1);
        
        // 尝试右子树
        path.Add('R');
        if (FindPath(root.right, target, path)) return true;
        path.RemoveAt(path.Count - 1);
        
        return false;
    }
}

var getDirections = function(root, startValue, destValue) {
    function findPath(node, target, path) {
        if (!node) return false;
        if (node.val === target) return true;
        
        path.push('L');
        if (findPath(node.left, target, path)) return true;
        path.pop();
        
        path.push('R');
        if (findPath(node.right, target, path)) return true;
        path.pop();
        
        return false;
    }
    
    let startPath = [];
    let destPath = [];
    
    findPath(root, startValue, startPath);
    findPath(root, destValue, destPath);
    
    let i = 0;
    while (i < startPath.length && i < destPath.length && startPath[i] === destPath[i]) {
        i++;
    }
    
    return 'U'.repeat(startPath.length - i) + destPath.slice(i).join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历整棵树来找到两个目标节点的路径，其中 n 是树中节点的数量
空间复杂度O(h)递归调用栈的深度为树的高度 h，路径字符串的长度也不超过 h

相关题目