LeetCode 2479: Maximum XOR of Two Non-Overlapping Subtrees

Explanation

To solve this problem, we can use a recursive approach to find the maximum XOR of two non-overlapping subtrees at each node. We will calculate the XOR of the subtree rooted at each node and compare it with the XOR of the other subtrees in the tree. At each node, we will consider two cases: either the left subtree or the right subtree is included in the XOR calculation.

We will traverse the tree in a post-order manner to calculate the XOR values of all subtrees. At each node, we will calculate the XOR values of the left and right subtrees and store them. Then, we will recursively find the maximum XOR of two non-overlapping subtrees for the current node.

Finally, we will return the maximum XOR value found during the traversal.

Algorithm:

1. Define a helper function dfs to calculate the XOR values of subtrees and find the maximum XOR of two non-overlapping subtrees at each node.
2. Initialize a global variable maxXOR to store the maximum XOR value found.
3. Traverse the tree in a post-order manner.
4. At each node, recursively calculate the XOR values of left and right subtrees.
5. Calculate the XOR value of the current subtree by XORing the subtree's value with the XOR values of left and right subtrees.
6. Update the maxXOR if a greater value is found.
7. Return the XOR value of the current subtree.
8. Return the maxXOR value as the final result.

Time Complexity:

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

Space Complexity:

The space complexity is O(N) due to the recursive stack space used during traversal.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    int maxXOR = 0;
    
    public int getMaxXOR(TreeNode root) {
        postOrder(root);
        return maxXOR;
    }
    
    private int postOrder(TreeNode node) {
        if (node == null) return 0;
        
        int leftXOR = postOrder(node.left);
        int rightXOR = postOrder(node.right);
        
        int currXOR = leftXOR ^ rightXOR ^ node.val;
        
        maxXOR = Math.max(maxXOR, Math.max(currXOR, Math.max(leftXOR, rightXOR)));
        
        return currXOR;
    }
}