Formatted question description: https://leetcode.ca/all/1660.html
Level
Medium
Description
You have a binary tree with a small defect. There is exactly one invalid node where its right child incorrectly points to another node at the same depth but to the invalid node’s right.
Given the root of the binary tree with this defect, root
, return the root of the binary tree after removing this invalid node and every node underneath it (minus the node it incorrectly points to).
Custom testing:
The test input is read as 3 lines:
TreeNode root
int fromNode
(not available tocorrectBinaryTree
)int toNode
(not available tocorrectBinaryTree
)
After the binary tree rooted at root
is parsed, the TreeNode
with value of fromNode
will have its right child pointer pointing to the TreeNode
with a value of toNode
. Then, root
is passed to correctBinaryTree
.
Example 1:
Input: root = [1,2,3], fromNode = 2, toNode = 3
Output: [1,null,3]
Explanation: The node with value 2 is invalid, so remove it.
Example 2:
Input: root = [8,3,1,7,null,9,4,2,null,null,null,5,6], fromNode = 7, toNode = 4
Output: [8,3,1,null,null,9,4,null,null,5,6]
Explanation: The node with value 7 is invalid, so remove it and the node underneath it, node 2.
Constraints:
- The number of nodes in the tree is in the range
[3, 10^4]
. -10^9 <= Node.val <= 10^9
- All
Node.val
are unique. fromNode != toNode
fromNode
andtoNode
will exist in the tree and will be on the same depth.toNode
is to the right offromNode
.fromNode.right
isnull
in the initial tree from the test data.
Algorithm
The idea is to traverse the BFS sequence. Because the error is the right pointer of a certain node, our level order traversal will change a little.
For each layer of nodes, we traverse from right to left. When traversing, we put the left and right children of the current node into the hashset
.
When traversing, it is also tested whether the right child of the left/right child already exists in the hashset.
- If it exists, it means that the right pointer of the left/right child points to a node in the current layer.
- We can remove the child who points to the wrong one.
Code
Java
public class Correct_a_Binary_Tree {
/**
* 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;
* }
* }
*/
class Solution {
public TreeNode correctBinaryTree(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
HashSet<TreeNode> set = new HashSet<>(); // per level, to store next level children
queue.offer(root);
int size = 1;
while (size > 0) {
TreeNode current = queue.poll();
size--;
if (current.right != null) {
set.add(current.right);
queue.offer(current.right);
if (set.contains(current.right.right)) {
current.right = null;
break;
}
}
if (current.left != null) {
set.add(current.left);
queue.offer(current.left);
if (set.contains(current.left.right)) {
current.left = null;
break;
}
}
if (size == 0) {
size = queue.size();
set = new HashSet<>();
}
}
return root;
}
}
}