1660. Correct a Binary Tree

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 to correctBinaryTree)
• int toNode (not available to correctBinaryTree)

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.

/**
 * 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* correctBinaryTree(TreeNode* root) {
        unordered_map<TreeNode*, int> level;
        unordered_map<TreeNode*, TreeNode*> par;
        queue<TreeNode*> q;
        q.push(root);
        par[root] = nullptr;
        level[root] = 0;
        while(!q.empty()) {
            int sz = q.size();
            while(sz--) {
                TreeNode* now = q.front(); q.pop();
                if(now->left) {
                    if(level.count(now->left)) {
                        TreeNode* p = par[now];
                        if(p->left == now) p->left = nullptr;
                        if(p->right == now) p->right = nullptr;
                        return root;
                    }
                    level[now->left] = level[now] + 1;
                    par[now->left] = now;
                    q.push(now->left);
                }
                if(now->right) {
                    if(level.count(now->right)) {
                        TreeNode* p = par[now];
                        if(p->left == now) p->left = nullptr;
                        if(p->right == now) p->right = nullptr;
                        return root;
                    }
                    level[now->right] = level[now] + 1;
                    par[now->right] = now;
                    q.push(now->right);
                }
            }
            
        }
        return root;
    }
};