实习+秋招刷题0011嘤嘤的新平衡树

0011嘤嘤的新平衡树
题目描述

给定一棵二叉树，二叉树的每个结点只有0或2个孩子。
你需要对每个结点赋值一个正整数，使得每个结点的左右子树权值和相等。
你需要返回所有结点的最小权值和对 10^9 +7取模的结果。
二叉树结点个数不超过10^5+5。
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256M，其他语言512M
示例1
输入例子：
{
   0,0,0}
输出例子：
3

关键解题思路
每结点的左右子树权值和相等，就可以看成是新满二叉树（如下图）。那我我们只需要计算这棵新满二叉树的深度，满二叉树的结点个数和等于
2^n-1。（n是深度）

Solution

import java.util.*;

/* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */

public class Solution {
   
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param tree TreeNode类 * @return int整型 */
    public int getTreeSum (TreeNode tree) {
   
        int mod = 1000000007;
        int ans =1;
        int height =getTreeHeight(tree);  //每结点的左右子树权值和相等，就可以看成是新满二叉树。
        //System.out.println(height);
        for(int i=0; i<height; i++){
   
            ans = 2*ans;
            ans = ans %mod;//取模要放在里面，因为后面存在ans大于mod的情况
        }
        //System.out.print(ans);
        return ans-1;
    }
    public int getTreeHeight (TreeNode tree) {
   
        if(tree==null){
   
            return 0;
        }
        int leftheight  = getTreeHeight(tree.left);
        int rightheight  = getTreeHeight(tree.right);
       return Math.max(leftheight, rightheight)+1;
    }
}