Practice/Google/Leetcode 1666. Change the Root of a Binary Tree

Leetcode 1666. Change the Root of a Binary Tree

CodingMust

Problem

You are given a binary tree where each node stores a reference to its parent and a list of its children. Your task is to transform this tree by designating a different node as the new root. When you change the root, all parent-child relationships along the path from the new root to the old root must be inverted.

Specifically, given the current root node and a target leaf node (which can be any node in the tree), modify the tree structure in-place so that leaf becomes the new root. All nodes along the path from leaf to root should have their parent-child relationships flipped.

Requirements

1. Modify the tree structure in-place
2. Return the new root node (the leaf parameter)
3. Maintain the tree structure for all nodes not on the path between old and new root
4. Each node should have its parent reference updated correctly
5. Each node's children list should reflect the new parent-child relationships

Constraints

• The tree contains at least 1 node and at most 10,000 nodes
• The leaf node is guaranteed to be in the tree rooted at root
• Node values are unique integers
• You must modify the tree in-place with O(1) extra space (excluding recursion stack)
• Time complexity should be O(h) where h is the height of the path from leaf to root

Examples

Example 1:

` Before: 1 /
2 3

After making node 2 the root: 2 | 1 | 3

Explanation: Node 2 becomes the root. Node 1 becomes a child of node 2. Node 3 remains a child of node 1. `

Example 2:

` Before: 1 | 2 | 3

After making node 3 the root: 3 | 2 | 1

Explanation: The chain is completely reversed. Node 3 is the new root with child 2, which has child 1. `

Example 3:

` Before: 1 /
2 3 /
4 5

After making node 4 the root: 4 | 2 /
1 5 | 3

Explanation: The path from 4 to 1 (4 -> 2 -> 1) is inverted. Node 5 and 3 remain in their original positions relative to their parents. `