小红的二叉树构造

[题目链接](https://www.nowcoder.com/practice/f798461d82c94959a1922efda1dd05eb)

思路

要构造一棵 $n$ 层的满二叉树，使得每一层的节点权值和都相等。

关键观察：第 $i$ 层（从 $0$ 开始计数）有 $2^i$ 个节点。设每层权值和为 $S$ ，则第 $i$ 层每个节点的平均权值为 $\frac{S}{2^i}$ 。为了让所有节点权值都是正整数， $S$ 必须是 $2^{n-1}$ 的倍数（因为最后一层有 $2^{n-1}$ 个节点）。

最简单的构造方案：取 $S = 2^{n-1}$ ，则第 $i$ 层的每个节点权值为 $\frac{2^{n-1}}{2^i} = 2^{n-1-i}$ 。

第 $0$ 层（根节点）：权值为 $2^{n-1}$
第 $1$ 层：每个节点权值为 $2^{n-2}$
...
第 $n-1$ 层（叶子层）：每个节点权值为 $1$

这样每一层的权值和都是 $2^{n-1}$ ，满足条件。

样例演示

输入 $n = 3$ ， $S = 2^2 = 4$ ：

第 $0$ 层： $4$ （和 = $4$ ）
第 $1$ 层： $2, 2$ （和 = $4$ ）
第 $2$ 层： $1, 1, 1, 1$ （和 = $4$ ）

输出 {4,2,2,1,1,1,1}，是一个合法解。题目示例的 {5,2,3,1,2,1,1} 也是合法解，有多解时返回任意一个即可。

代码

C++
Java

class Solution {
public:
    TreeNode* create(int n) {
        return build(0, n);
    }

    TreeNode* build(int level, int n) {
        if (level >= n) return nullptr;
        int val = 1 << (n - 1 - level);
        TreeNode* node = new TreeNode(val);
        node->left = build(level + 1, n);
        node->right = build(level + 1, n);
        return node;
    }
};

import java.util.*;

public class Solution {
    public TreeNode create (int n) {
        return build(0, n);
    }

    private TreeNode build(int level, int n) {
        if (level >= n) return null;
        int val = 1 << (n - 1 - level);
        TreeNode node = new TreeNode(val);
        node.left = build(level + 1, n);
        node.right = build(level + 1, n);
        return node;
    }
}

复杂度分析

时间复杂度： $O(2^n)$ 。需要构造满二叉树的所有节点，共 $2^n - 1$ 个。
空间复杂度： $O(2^n)$ 。存储整棵满二叉树需要 $2^n - 1$ 个节点，递归栈深度为 $O(n)$ 。