ou are given the root of a binary tree with n nodes. Each node is uniquely assigned a value from 1 to n. You are also given an integer startValue representing the value of the start node s, and a different integer destValue representing the value of the destination node t.
Find the shortest path starting from node s and ending at node t. Generate step-by-step directions of such path as a string consisting of only the uppercase letters 'L', 'R', and 'U'. Each letter indicates a specific direction:
'L' means to go from a node to its left child node.'R' means to go from a node to its right child node.'U' means to go from a node to its parent node.Return the step-by-step directions of the shortest path from node s to node t.
Example 1:
Input: root = [5,1,2,3,null,6,4], startValue = 3, destValue = 6 Output: "UURL" Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.
Example 2:
Input: root = [2,1], startValue = 2, destValue = 1 Output: "L" Explanation: The shortest path is: 2 → 1.
Constraints:
n.2 <= n <= 1051 <= Node.val <= n1 <= startValue, destValue <= nstartValue != destValue# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def getDirections(self, root, startValue, destValue): def lca(node): if not node: return None if node.val == startValue or node.val == destValue: return node left = lca(node.left) right = lca(node.right) if left and right: return node return left or right def findPath(node, target, path): if not node: return False if node.val == target: return True path.append("L") if findPath(node.left, target, path): return True path.pop() path.append("R") if findPath(node.right, target, path): return True path.pop() return False ancestor = lca(root) pathStart = [] pathDest = [] findPath(ancestor, startValue, pathStart) findPath(ancestor, destValue, pathDest) return "U" * len(pathStart) + "".join(pathDest)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。