Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/1666.html
1666. Change the Root of a Binary Tree
Given the root of a binary tree and a leaf node, reroot the tree so that the leaf is the new root.
You can reroot the tree with the following steps for each node cur on the path starting from the leaf up to the root excluding the root:
If cur has a left child, then that child becomes cur's right child. Note that it is guaranteed that cur will have at most one child.
cur's original parent becomes cur's left child.
Return the new root of the rerooted tree.
Note: Ensure that your solution sets the Node.parent pointers correctly after rerooting or you will receive "Wrong Answer".
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 7
Output: [7,2,null,5,4,3,6,null,null,null,1,null,null,0,8]
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], leaf = 0
Output: [0,1,null,3,8,5,null,null,null,6,2,null,null,7,4]
Constraints:
The number of nodes in the tree is in the range [2, 100].
-109 <= Node.val <= 109
All Node.val are unique.
leaf exist in the tree.
Algorithm
The dfs process of this question should actually go from leaf up to root. For each node, we need to change its left, right and parent. node->parent should point to the predecessor node of node (that is, the child on the leaf->root path). node->left should point to the upward path (that is, the original parent). node->right should point to its other child (that is, the child on the non-leaf->root path). Then recursively process the next node on the leaf->root path.
Another pitfall of this question is that the question requires the handling of root, which is slightly different from the handling of other nodes. Just point node->parent to the predecessor node, and then set the child on the leaf->root path to NULL. It is not necessary to migrate the child on the non-path to the right node.
Code
-
Todo -
Todo -
Todo