Maximum Non-Adjacent Tree Sum - Amazon Top Interview Questions

                        Solution in C++ :

vector<int> helper(Tree* root, int& ans) {
    if (root == NULL) {
        return {0, 0};
    }
    if (root->left == root->right) {
        ans = max(ans, root->val);
        return {root->val, 0};
    }
    auto lef = helper(root->left, ans);
    auto ri = helper(root->right, ans);

    int taking = lef[1] + ri[1] + root->val;
    int leaving = max(lef[0], lef[1]) + max(ri[0], ri[1]);

    ans = max({ans, taking, leaving});

    return {taking, leaving};
}
int solve(Tree* root) {
    int ans = 0;
    helper(root, ans);
    return ans;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(Tree root) {
        dfs(root);
        return max;
    }

    int max = 0;
    public int[] dfs(Tree root) {
        if (root == null)
            return new int[] {0, 0};

        int[] left = dfs(root.left);
        int[] right = dfs(root.right);

        int[] res = new int[] {Math.max(left[0], left[1]) + Math.max(right[0], right[1]),
            left[0] + right[0] + root.val};
        max = Math.max(res[0], res[1]);

        return res;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, root):
        def dfs(node):
            if node:
                left_sum1, left_sum2 = dfs(node.left)
                right_sum1, right_sum2 = dfs(node.right)

                sum1 = left_sum2 + right_sum2 + node.val

                sum2 = max(
                    left_sum1 + right_sum1,
                    left_sum1 + right_sum2,
                    left_sum2 + right_sum1,
                    left_sum2 + right_sum2,
                )

                return sum1, sum2
            else:
                return 0, 0

        (sum1, sum2) = dfs(root)

        return max(sum1, sum2)