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

Problem #

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

Problem Summary #

You are given the root node root of a binary tree. This binary tree has a total of n nodes. Each node has a value that is an integer from 1 to n, and all values are distinct. You are given an integer startValue, representing the value of the start node s, and another different integer destValue, representing the value of the destination node t.

Find the shortest path from node s to node t, and return the direction of each step as a string. Each step is represented by the uppercase letters ‘L’, ‘R’, and ‘U’, which respectively indicate a direction:

• ‘L’ means going from a node to its left child node.
• ‘R’ means going from a node to its right child node.
• ‘U’ means going from a node to its parent node.

Return the directions for each step of the shortest path from s to t.

Solution Approach #

• The shortest path from one node to another node in a binary tree can always be divided into two parts (possibly empty): from the start node upward to the lowest common ancestor of the two nodes, and then from the lowest common ancestor downward to the destination node.
• First, find path1 between the start node s and the common ancestor node, and path2 between the common ancestor node and the destination t. Then remove the common prefix of the two paths. If the start node s and destination node t are on different branches, there is no common prefix. If they are on the same branch, then the common prefix should be removed from the final answer.
• After removing the common prefix, the output format of the final answer needs to be adjusted. Since the problem requires outputting U from the start node to the common ancestor node, change this entire segment path1 to U, then concatenate it with the path2 string. The resulting string is the shortest path directions for each step from s to t.

Code #

package leetcode

import (
	"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func getDirections(root *TreeNode, startValue int, destValue int) string {
	sPath, dPath := make([]byte, 0), make([]byte, 0)
	findPath(root, startValue, &sPath)
	findPath(root, destValue, &dPath)
	size, i := min(len(sPath), len(dPath)), 0
	for i < size {
		if sPath[len(sPath)-1-i] == dPath[len(dPath)-1-i] {
			i++
		} else {
			break
		}
	}
	sPath = sPath[:len(sPath)-i]
	replace(sPath)
	dPath = dPath[:len(dPath)-i]
	reverse(dPath)
	sPath = append(sPath, dPath...)
	return string(sPath)
}

func findPath(root *TreeNode, value int, path *[]byte) bool {
	if root.Val == value {
		return true
	}

	if root.Left != nil && findPath(root.Left, value, path) {
		*path = append(*path, 'L')
		return true
	}

	if root.Right != nil && findPath(root.Right, value, path) {
		*path = append(*path, 'R')
		return true
	}

	return false
}

func reverse(path []byte) {
	left, right := 0, len(path)-1
	for left < right {
		path[left], path[right] = path[right], path[left]
		left++
		right--
	}
}

func replace(path []byte) {
	for i := 0; i < len(path); i++ {
		path[i] = 'U'
	}
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}