Trace the Route From the Root to a Chosen Node
Implement routeTo
You are given the root of a binary tree in which every node has a distinct value, and an integer target. Return the list of node values on the route from the root down to the node holding target, starting with the root's value and ending with target. If the tree has no node with that value, return an empty list.
A depth-first search with backtracking finds the route directly: keep a path, add a node when you enter it, and take it off again when the target is not below it.
Example 1:
Input: root = [14,9,20,5,11,17,25,3,null,null,13], target = 13
Output: [14,9,11,13]
Example 2:
Input: root = [14,9,20], target = 14
Output: [14]
Example 3:
Input: root = [14,9,20], target = 8
Output: []
+ 12 hidden test cases run on Submit.
Constraints:
- ●
0 ≤ number of nodes ≤ 100 - ●
1 ≤ node.val ≤ 1000, and all node values in the tree are distinct; 1 ≤ target ≤ 1000 - ●
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ●
Return the values on the route from the root down to the node whose value is target (both ends included), in order from the root. If no node has that value, return an empty list
root =
target =