You are given the root of a binary tree, and a target node leaf that exists in the tree. Your task is to "change the root" of the tree to this leaf node, such that the parent-child relationships along the path from the original root to leaf are reversed. All other parts of the tree should remain unchanged.
In other words, after the operation, leaf becomes the new root, and for every node along the path from the old root to leaf, the child-parent pointers are reversed. The rest of the tree (subtrees not on this path) should remain attached to their original parents.
Constraints:
leaf node is guaranteed to exist in the tree.leaf.
The main challenge is to reverse the parent-child pointers along the path from the original root to the given leaf. We need to be careful to not disturb the rest of the tree. Brute-forcing by reconstructing the entire tree is unnecessary and error-prone.
Instead, we should focus on:
leaf.Let's break down the solution step-by-step:
leaf node.leaf up to the root along the path.leaf becomes the new root. Return it.We use a stack or list to store the path for easy reversal. This approach is efficient and only modifies the necessary pointers.
Consider the following tree:
1
/ \
2 3
/
4
If leaf = 4, the path is [1, 2, 4].
4
/
2
/
1
\
3
The rest of the tree (node 3) remains attached to node 1, which is now a child of 2, which is a child of 4.
Brute-force approach: Rebuilding the entire tree would take O(N) time and O(N) space, where N is the number of nodes.
Optimized approach (pointer reversal):
leaf.leaf.
The key insight is to reverse the parent-child pointers along the path from the original root to the target leaf node, rather than rebuilding the whole tree. This approach is both time and space efficient, requiring only O(H) operations, and carefully preserves the rest of the tree. The solution demonstrates how understanding pointer manipulation in trees enables elegant in-place transformations.
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def changeRoot(self, root: TreeNode, leaf: TreeNode) -> TreeNode:
# Find path from root to leaf
path = []
def dfs(node, target):
if not node:
return False
path.append(node)
if node == target:
return True
if dfs(node.left, target) or dfs(node.right, target):
return True
path.pop()
return False
dfs(root, leaf)
# Reverse the path pointers
prev = None
for i in range(len(path)-1, -1, -1):
curr = path[i]
parent = path[i-1] if i > 0 else None
# Detach curr from its parent
if parent:
if parent.left == curr:
parent.left = None
else:
parent.right = None
# Attach previous node as left child (or right, but left is fine)
if prev:
# Attach prev as left or right if curr's left is None
if curr.left is None:
curr.left = prev
else:
curr.right = prev
prev = curr
return leaf
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* changeRoot(TreeNode* root, TreeNode* leaf) {
vector<TreeNode*> path;
// Find path from root to leaf
function<bool(TreeNode*, TreeNode*)> dfs = [&](TreeNode* node, TreeNode* target) {
if (!node) return false;
path.push_back(node);
if (node == target) return true;
if (dfs(node->left, target) || dfs(node->right, target)) return true;
path.pop_back();
return false;
};
dfs(root, leaf);
TreeNode* prev = nullptr;
for (int i = path.size() - 1; i >= 0; --i) {
TreeNode* curr = path[i];
TreeNode* parent = (i > 0) ? path[i-1] : nullptr;
// Detach curr from its parent
if (parent) {
if (parent->left == curr) parent->left = nullptr;
else parent->right = nullptr;
}
// Attach prev as left or right child
if (prev) {
if (!curr->left) curr->left = prev;
else curr->right = prev;
}
prev = curr;
}
return leaf;
}
};
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
import java.util.*;
class Solution {
public TreeNode changeRoot(TreeNode root, TreeNode leaf) {
List<TreeNode> path = new ArrayList<>();
// Find path from root to leaf
boolean dfs(TreeNode node, TreeNode target, List<TreeNode> pathList) {
if (node == null) return false;
pathList.add(node);
if (node == target) return true;
if (dfs(node.left, target, pathList) || dfs(node.right, target, pathList)) return true;
pathList.remove(pathList.size() - 1);
return false;
}
dfs(root, leaf, path);
TreeNode prev = null;
for (int i = path.size() - 1; i >= 0; --i) {
TreeNode curr = path.get(i);
TreeNode parent = (i > 0) ? path.get(i-1) : null;
// Detach curr from its parent
if (parent != null) {
if (parent.left == curr) parent.left = null;
else parent.right = null;
}
// Attach prev as left or right child
if (prev != null) {
if (curr.left == null) curr.left = prev;
else curr.right = prev;
}
prev = curr;
}
return leaf;
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} leaf
* @return {TreeNode}
*/
var changeRoot = function(root, leaf) {
const path = [];
// Find path from root to leaf
function dfs(node, target) {
if (!node) return false;
path.push(node);
if (node === target) return true;
if (dfs(node.left, target) || dfs(node.right, target)) return true;
path.pop();
return false;
}
dfs(root, leaf);
let prev = null;
for (let i = path.length - 1; i >= 0; --i) {
const curr = path[i];
const parent = (i > 0) ? path[i-1] : null;
// Detach curr from its parent
if (parent) {
if (parent.left === curr) parent.left = null;
else parent.right = null;
}
// Attach prev as left or right child
if (prev) {
if (curr.left === null) curr.left = prev;
else curr.right = prev;
}
prev = curr;
}
return leaf;
};