LeetCode 1660: Correct a Binary Tree

Explanation:

To correct a binary tree, we need to find and remove the edge causing the tree to be invalid. An invalid binary tree is one where there is a node with two parents. To solve this problem, we can perform a depth-first search (DFS) traversal of the tree while keeping track of the parent of each node. If we encounter a node whose parent is already set, that means we have found the invalid node. We can then identify the two parents and remove the edge connecting the invalid node to one of its parents.

Algorithm:

1. Initialize a HashMap to store the parent of each node.
2. Perform a DFS traversal of the tree.
3. While traversing:
   • If the current node is already in the HashMap, it means we have found the invalid node.
   • Retrieve the two parents of the invalid node and remove the edge connecting it to one of the parents.
4. Return the corrected tree.

Time Complexity:

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree.

Space Complexity:

The space complexity of this solution is O(n), where n is the number of nodes in the binary tree.

: :

class Solution {
    public TreeNode correctBinaryTree(TreeNode root) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        return dfs(root, null, parent);
    }

    private TreeNode dfs(TreeNode node, TreeNode prev, Map<TreeNode, TreeNode> parent) {
        if (node == null) return null;
        
        if (parent.containsKey(node)) {
            TreeNode p = parent.get(node);
            if (p.left == node) p.left = null;
            else p.right = null;
            return null;
        }
        
        parent.put(node, prev);
        
        node.left = dfs(node.left, node, parent);
        node.right = dfs(node.right, node, parent);
        
        return node;
    }
}