Description#
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. cur
's original parent becomes cur
's left child. Note that in this process the original parent's pointer to cur
becomes null
, making it have at most one 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:
![](https://spcdn.pages.dev/leetcode/problems/1666.Change%20the%20Root%20of%20a%20Binary%20Tree/images/fliptree.png)
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.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| """
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""
class Solution:
def flipBinaryTree(self, root: "Node", leaf: "Node") -> "Node":
cur = leaf
p = cur.parent
while cur != root:
gp = p.parent
if cur.left:
cur.right = cur.left
cur.left = p
p.parent = cur
if p.left == cur:
p.left = None
elif p.right == cur:
p.right = None
cur = p
p = gp
leaf.parent = None
return leaf
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| /*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
};
*/
class Solution {
public Node flipBinaryTree(Node root, Node leaf) {
Node cur = leaf;
Node p = cur.parent;
while (cur != root) {
Node gp = p.parent;
if (cur.left != null) {
cur.right = cur.left;
}
cur.left = p;
p.parent = cur;
if (p.left == cur) {
p.left = null;
} else if (p.right == cur) {
p.right = null;
}
cur = p;
p = gp;
}
leaf.parent = null;
return leaf;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| /*
// Definition for a Node->
class Node {
public:
int val;
Node* left;
Node* right;
Node* parent;
};
*/
class Solution {
public:
Node* flipBinaryTree(Node* root, Node* leaf) {
Node* cur = leaf;
Node* p = cur->parent;
while (cur != root) {
Node* gp = p->parent;
if (cur->left) {
cur->right = cur->left;
}
cur->left = p;
p->parent = cur;
if (p->left == cur) {
p->left = nullptr;
} else if (p->right == cur) {
p->right = nullptr;
}
cur = p;
p = gp;
}
leaf->parent = nullptr;
return leaf;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| /**
* // Definition for a Node.
* function Node(val) {
* this.val = val;
* this.left = null;
* this.right = null;
* this.parent = null;
* };
*/
/**
* @param {Node} node
* @return {Node}
*/
var flipBinaryTree = function (root, leaf) {
let cur = leaf;
let p = cur.parent;
while (cur != root) {
const gp = p.parent;
if (cur.left != null) {
cur.right = cur.left;
}
cur.left = p;
p.parent = cur;
if (p.left == cur) {
p.left = null;
} else if (p.right == cur) {
p.right = null;
}
cur = p;
p = gp;
}
leaf.parent = null;
return leaf;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| /*
// Definition for a Node.
public class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
*/
public class Solution {
public Node FlipBinaryTree(Node root, Node leaf) {
Node cur = leaf;
Node p = cur.parent;
while (cur != root) {
Node gp = p.parent;
if (cur.left != null) {
cur.right = cur.left;
}
cur.left = p;
p.parent = cur;
if (p.left == cur) {
p.left = null;
} else if (p.right == cur) {
p.right = null;
}
cur = p;
p = gp;
}
leaf.parent = null;
return leaf;
}
}
|