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 <= 10⁵
1 <= Node.val <= n
All the values in the tree are unique.
1 <= startValue, destValue <= n
startValue != destValue

Solution: Lowest common ancestor

It’s no hard to see that the shortest path is from the start node to the lowest common ancestor (LCA) of (start, end), then to the end node. The key is to find the LCA while finding paths from root to two nodes.

We can use recursion to find/build a path from root to a target node.
The common prefix of these two paths is the path from root to the LCA that we need to remove from the shortest path.
e.g.
root to start “LLRLR”
root to dest “LLLR”
common prefix is “LL”, after removing, it becomes:
LCA to start “RLR”
LCA to dest “LR”
Final path becomes “UUU” + “LR” = “UUULR”

The final step is to replace the L/R with U for the start path since we are moving up and then concatenate with the target path.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string getDirections(TreeNode* root, int startValue, int destValue) {

string startPath;

string destPath;

buildPath(root, startValue, startPath);

buildPath(root, destValue, destPath);

// Remove common suffix (shared path from root to LCA)

while (!startPath.empty() && !destPath.empty()

&& startPath.back() == destPath.back()) {

startPath.pop_back();

destPath.pop_back();

}

reverse(begin(destPath), end(destPath));

return string(startPath.size(), 'U') + destPath;

}

private:

bool buildPath(TreeNode* root, int t, string& path) {

if (!root) return false;

if (root->val == t) return true;

if (buildPath(root->left, t, path)) {

path.push_back('L');

return true;

} else if (buildPath(root->right, t, path)) {

path.push_back('R');

return true;

}

return false;

}

};

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the binary tree.

Solution 1: Recursion

Time complexity: O(n)

Space complexity: O(h)

For a given root, recursively call LCA(root.left, p, q) and LCA(root.right, p, q)

if both returns a valid node which means p, q are in different subtrees, then root will be their LCA.

if only one valid node returns, which means p, q are in the same subtree, return that valid node as their LCA.

C++

// Author: Huahua

class Solution {

public:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

if (!root || root == p || root == q) return root;

TreeNode* l = lowestCommonAncestor(root->left, p, q);

TreeNode* r = lowestCommonAncestor(root->right, p, q);

if (l && r) return root;

return l ? l : r;

}

};

Java

// Author: Huahua

class Solution {

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

if (root == null || root == p || root == q) return root;

TreeNode l = lowestCommonAncestor(root.left, p, q);

TreeNode r = lowestCommonAncestor(root.right, p, q);

if (l == null || r == null) return l == null ? r : l;

return root;

}

Python3

# Author: Huahua

class Solution:

def lowestCommonAncestor(self, root, p, q):

if any((not root, root == p, root == q)): return root

l = self.lowestCommonAncestor(root.left, p, q)

r = self.lowestCommonAncestor(root.right, p, q)

if not l or not r: return l if l else r

return root

Posts tagged as “LCA”

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

Solution: Lowest common ancestor

C++

花花酱 LeetCode 236. Lowest Common Ancestor of a Binary Tree

Problem

Solution 1: Recursion

C++

Java

Python3

Related Problems: