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
}