2096. Step-By-Step Directions From a Binary Tree Node to Another
给一个二元树的root，包含n个node
并把1~n的值分配给这些node
给予startValue、destValue
请列出startValue到destValue的路径
'L'代表走向左子节点
'R'代表走向右子节点
'U'代表走往parent node
思路:
列出root分别到startValue、destValue的路径
接着排除掉相同的prefix路径
接着把到startValue剩下的路径全部换成'U'
接到到destValue剩下的路径
就可以得到答案了
golang code :
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func getDirections(root *TreeNode, startValue int, destValue int) string {
path1, path2 := make([]byte, 0, 100000), make([]byte, 0, 100000)
find(root, startValue, &path1)
find(root, destValue, &path2)
var i, j int
n, m := len(path1), len(path2)
var res strings.Builder
for i < n && j < m && path1[i] == path2[j] {
i++
j++
}
for i < n {
res.WriteByte('U')
i++
}
res.Write(path2[j:m])
return res.String()
}
func find(node *TreeNode, target int, path *[]byte) bool {
if node == nil {
return false
}
if node.Val == target {
return true
}
*path = append(*path, 'L')
res := find(node.Left, target, path)
if res {
return true
}
*path = (*path)[:len(*path)-1]
*path = append(*path, 'R')
res = find(node.Right, target, path)
if res {
return true
}
*path = (*path)[:len(*path)-1]
return false
}