Description
You 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:
- The number of nodes in the tree is
n.
2 <= n <= 1051 <= Node.val <= n- All the values in the tree are unique.
1 <= startValue, destValue <= nstartValue != destValue
Solutions
Solution 1: Lowest Common Ancestor + DFS
We can first find the lowest common ancestor of nodes startValue and destValue, denoted as node. Then, starting from node, we find the paths to startValue and destValue respectively. The path from startValue to node will consist of a number of Us, and the path from node to destValue will be the path. Finally, we concatenate these two paths.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
PythonJavaC++GoTypeScriptJavaScript
# 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: Optional[TreeNode], startValue: int, destValue: int
) -> str:
def lca(node: Optional[TreeNode], p: int, q: int):
if node is None or node.val in (p, q):
return node
left = lca(node.left, p, q)
right = lca(node.right, p, q)
if left and right:
return node
return left or right
def dfs(node: Optional[TreeNode], x: int, path: List[str]):
if node is None:
return False
if node.val == x:
return True
path.append("L")
if dfs(node.left, x, path):
return True
path[-1] = "R"
if dfs(node.right, x, path):
return True
path.pop()
return False
node = lca(root, startValue, destValue)
path_to_start = []
path_to_dest = []
dfs(node, startValue, path_to_start)
dfs(node, destValue, path_to_dest)
return "U" * len(path_to_start) + "".join(path_to_dest)(code-box)
class Solution {
public String getDirections(TreeNode root, int startValue, int destValue) {
TreeNode node = lca(root, startValue, destValue);
StringBuilder pathToStart = new StringBuilder();
StringBuilder pathToDest = new StringBuilder();
dfs(node, startValue, pathToStart);
dfs(node, destValue, pathToDest);
return "U".repeat(pathToStart.length()) + pathToDest.toString();
}
private TreeNode lca(TreeNode node, int p, int q) {
if (node == null || node.val == p || node.val == q) {
return node;
}
TreeNode left = lca(node.left, p, q);
TreeNode right = lca(node.right, p, q);
if (left != null && right != null) {
return node;
}
return left != null ? left : right;
}
private boolean dfs(TreeNode node, int x, StringBuilder path) {
if (node == null) {
return false;
}
if (node.val == x) {
return true;
}
path.append('L');
if (dfs(node.left, x, path)) {
return true;
}
path.setCharAt(path.length() - 1, 'R');
if (dfs(node.right, x, path)) {
return true;
}
path.deleteCharAt(path.length() - 1);
return false;
}
}(code-box)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
string getDirections(TreeNode* root, int startValue, int destValue) {
TreeNode* node = lca(root, startValue, destValue);
string pathToStart, pathToDest;
dfs(node, startValue, pathToStart);
dfs(node, destValue, pathToDest);
return string(pathToStart.size(), 'U') + pathToDest;
}
private:
TreeNode* lca(TreeNode* node, int p, int q) {
if (node == nullptr || node->val == p || node->val == q) {
return node;
}
TreeNode* left = lca(node->left, p, q);
TreeNode* right = lca(node->right, p, q);
if (left != nullptr && right != nullptr) {
return node;
}
return left != nullptr ? left : right;
}
bool dfs(TreeNode* node, int x, string& path) {
if (node == nullptr) {
return false;
}
if (node->val == x) {
return true;
}
path.push_back('L');
if (dfs(node->left, x, path)) {
return true;
}
path.back() = 'R';
if (dfs(node->right, x, path)) {
return true;
}
path.pop_back();
return false;
}
};(code-box)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getDirections(root *TreeNode, startValue int, destValue int) string {
var lca func(node *TreeNode, p, q int) *TreeNode
lca = func(node *TreeNode, p, q int) *TreeNode {
if node == nil || node.Val == p || node.Val == q {
return node
}
left := lca(node.Left, p, q)
right := lca(node.Right, p, q)
if left != nil && right != nil {
return node
}
if left != nil {
return left
}
return right
}
var dfs func(node *TreeNode, x int, path *[]byte) bool
dfs = func(node *TreeNode, x int, path *[]byte) bool {
if node == nil {
return false
}
if node.Val == x {
return true
}
*path = append(*path, 'L')
if dfs(node.Left, x, path) {
return true
}
(*path)[len(*path)-1] = 'R'
if dfs(node.Right, x, path) {
return true
}
*path = (*path)[:len(*path)-1]
return false
}
node := lca(root, startValue, destValue)
pathToStart := []byte{}
pathToDest := []byte{}
dfs(node, startValue, &pathToStart)
dfs(node, destValue, &pathToDest)
return string(bytes.Repeat([]byte{'U'}, len(pathToStart))) + string(pathToDest)
}(code-box)
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getDirections(root: TreeNode | null, startValue: number, destValue: number): string {
const lca = (node: TreeNode | null, p: number, q: number): TreeNode | null => {
if (node === null || [p, q].includes(node.val)) {
return node;
}
const left = lca(node.left, p, q);
const right = lca(node.right, p, q);
return left && right ? node : (left ?? right);
};
const dfs = (node: TreeNode | null, x: number, path: string[]): boolean => {
if (node === null) {
return false;
}
if (node.val === x) {
return true;
}
path.push('L');
if (dfs(node.left, x, path)) {
return true;
}
path[path.length - 1] = 'R';
if (dfs(node.right, x, path)) {
return true;
}
path.pop();
return false;
};
const node = lca(root, startValue, destValue);
const pathToStart: string[] = [];
const pathToDest: string[] = [];
dfs(node, startValue, pathToStart);
dfs(node, destValue, pathToDest);
return 'U'.repeat(pathToStart.length) + pathToDest.join('');
}(code-box)
/**
* 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 = (node, p, q) => {
if (node === null || [p, q].includes(node.val)) {
return node;
}
const left = lca(node.left, p, q);
const right = lca(node.right, p, q);
return left && right ? node : (left ?? right);
};
const dfs = (node, x, path) => {
if (node === null) {
return false;
}
if (node.val === x) {
return true;
}
path.push('L');
if (dfs(node.left, x, path)) {
return true;
}
path[path.length - 1] = 'R';
if (dfs(node.right, x, path)) {
return true;
}
path.pop();
return false;
};
const node = lca(root, startValue, destValue);
const pathToStart = [];
const pathToDest = [];
dfs(node, startValue, pathToStart);
dfs(node, destValue, pathToDest);
return 'U'.repeat(pathToStart.length) + pathToDest.join('');
};(code-box)
Solution 2: Lowest Common Ancestor + DFS (Optimized)
We can start from root, find the paths to startValue and destValue, denoted as pathToStart and pathToDest, respectively. Then, remove the longest common prefix of pathToStart and pathToDest. At this point, the length of pathToStart is the number of Us in the answer, and the path of pathToDest is the path in the answer. We just need to concatenate these two paths.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
PythonJavaC++GoTypeScriptJavaScript
# 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: Optional[TreeNode], startValue: int, destValue: int
) -> str:
def dfs(node: Optional[TreeNode], x: int, path: List[str]):
if node is None:
return False
if node.val == x:
return True
path.append("L")
if dfs(node.left, x, path):
return True
path[-1] = "R"
if dfs(node.right, x, path):
return True
path.pop()
return False
path_to_start = []
path_to_dest = []
dfs(root, startValue, path_to_start)
dfs(root, destValue, path_to_dest)
i = 0
while (
i < len(path_to_start)
and i < len(path_to_dest)
and path_to_start[i] == path_to_dest[i]
):
i += 1
return "U" * (len(path_to_start) - i) + "".join(path_to_dest[i:])(code-box)
class Solution {
public String getDirections(TreeNode root, int startValue, int destValue) {
StringBuilder pathToStart = new StringBuilder();
StringBuilder pathToDest = new StringBuilder();
dfs(root, startValue, pathToStart);
dfs(root, destValue, pathToDest);
int i = 0;
while (i < pathToStart.length() && i < pathToDest.length()
&& pathToStart.charAt(i) == pathToDest.charAt(i)) {
++i;
}
return "U".repeat(pathToStart.length() - i) + pathToDest.substring(i);
}
private boolean dfs(TreeNode node, int x, StringBuilder path) {
if (node == null) {
return false;
}
if (node.val == x) {
return true;
}
path.append('L');
if (dfs(node.left, x, path)) {
return true;
}
path.setCharAt(path.length() - 1, 'R');
if (dfs(node.right, x, path)) {
return true;
}
path.deleteCharAt(path.length() - 1);
return false;
}
}(code-box)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
string getDirections(TreeNode* root, int startValue, int destValue) {
string pathToStart, pathToDest;
dfs(root, startValue, pathToStart);
dfs(root, destValue, pathToDest);
int i = 0;
while (i < pathToStart.size() && i < pathToDest.size() && pathToStart[i] == pathToDest[i]) {
i++;
}
return string(pathToStart.size() - i, 'U') + pathToDest.substr(i);
}
private:
bool dfs(TreeNode* node, int x, string& path) {
if (node == nullptr) {
return false;
}
if (node->val == x) {
return true;
}
path.push_back('L');
if (dfs(node->left, x, path)) {
return true;
}
path.back() = 'R';
if (dfs(node->right, x, path)) {
return true;
}
path.pop_back();
return false;
}
};(code-box)
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getDirections(root *TreeNode, startValue int, destValue int) string {
var dfs func(node *TreeNode, x int, path *[]byte) bool
dfs = func(node *TreeNode, x int, path *[]byte) bool {
if node == nil {
return false
}
if node.Val == x {
return true
}
*path = append(*path, 'L')
if dfs(node.Left, x, path) {
return true
}
(*path)[len(*path)-1] = 'R'
if dfs(node.Right, x, path) {
return true
}
*path = (*path)[:len(*path)-1]
return false
}
pathToStart := []byte{}
pathToDest := []byte{}
dfs(root, startValue, &pathToStart)
dfs(root, destValue, &pathToDest)
i := 0
for i < len(pathToStart) && i < len(pathToDest) && pathToStart[i] == pathToDest[i] {
i++
}
return string(bytes.Repeat([]byte{'U'}, len(pathToStart)-i)) + string(pathToDest[i:])
}(code-box)
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function getDirections(root: TreeNode | null, startValue: number, destValue: number): string {
const dfs = (node: TreeNode | null, x: number, path: string[]): boolean => {
if (node === null) {
return false;
}
if (node.val === x) {
return true;
}
path.push('L');
if (dfs(node.left, x, path)) {
return true;
}
path[path.length - 1] = 'R';
if (dfs(node.right, x, path)) {
return true;
}
path.pop();
return false;
};
const pathToStart: string[] = [];
const pathToDest: string[] = [];
dfs(root, startValue, pathToStart);
dfs(root, destValue, pathToDest);
let i = 0;
while (pathToStart[i] === pathToDest[i]) {
++i;
}
return 'U'.repeat(pathToStart.length - i) + pathToDest.slice(i).join('');
}(code-box)
/**
* 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 dfs = (node, x, path) => {
if (node === null) {
return false;
}
if (node.val === x) {
return true;
}
path.push('L');
if (dfs(node.left, x, path)) {
return true;
}
path[path.length - 1] = 'R';
if (dfs(node.right, x, path)) {
return true;
}
path.pop();
return false;
};
const pathToStart = [];
const pathToDest = [];
dfs(root, startValue, pathToStart);
dfs(root, destValue, pathToDest);
let i = 0;
while (pathToStart[i] === pathToDest[i]) {
++i;
}
return 'U'.repeat(pathToStart.length - i) + pathToDest.slice(i).join('');
};(code-box)
