腾讯音乐笔试题

第三题：
求二叉树最小权值和mod1e9+7 二叉树的子节点要么一个没有要么全有；
只能过15%；考试结束知道问题原因了-_- 原因是在进行左右值相等的时候是根据子节点的子节点去平衡的，应该是递归这个子树，真是乌鱼子 正确解法应该是 加个memo 可以是hashMap 用来存当前节点的树的权值；
思路：
- 进行后序遍历判断当前根节点的两个字节的权值和点是否相等：
1. 如果相等那个当前根节点的值为1 返回当前根节点的二叉树的权值；
2. 如果不想等那个让小的那边的根结点的值等于就用大的权值 - 小的左右子树的权值之和；
之后再用递归递归一遍得到结果；
害 考试没想起来 不知道现在这个解法是正确的不 欢迎大佬解答！！！！！

public class Solution {
    public int getTreeSum (TreeNode root) {
        if(root == null) return 0;
        final double mod = 1e9 + 7;
        make(root);
        int res = (int)(getres(root) % mod);
        return res;
    }

    int getres(TreeNode root){
        if(root == null) return 0;
        int left = getres(root.left);
        int right = getres(root.right);
        return root.val + left + right;
    }

    int make(TreeNode root){
        if(root == null) return 0;
        int left = make(root.left);
        int right = make(root.right);
        if(left == right){
            root.val = 1;
            return root.val + left + right;
        }else {
            root.val = 1;
            int l = 0,r = 0;
            if(left > right){
                if(root.right.left != null)
                    l = root.right.left.val;
                if(root.right.right != null)
                    r = root.right.right.val;
                root.right.val = left - l - r;
            }else {
                if(root.left.left != null)
                    l = root.left.left.val;
                if(root.left.right != null)
                    r = root.left.right.val;

                root.left.val = right - l - r;
            }
        }
        return root.val + root.left.val + root.right.val;
    }
}