补全完全二叉树

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

思路

给定一棵二叉树，要求添加尽可能少的节点使其成为完全二叉树。

完全二叉树的编号性质

在完全二叉树中，如果把根节点编号为 ，则对于编号为 的节点，其左孩子编号为 ，右孩子编号为 。一棵有 个节点的完全二叉树，恰好包含编号 到 的所有节点。

确定目标大小

对原始二叉树做 BFS，为每个节点按照"根=1，左孩子=2i，右孩子=2i+1"的规则分配编号。记所有节点编号的最大值为 。

要使原树成为完全二叉树，完全二叉树的节点总数至少为 （否则某个原有节点就会落在完全二叉树之外）。而恰好取 个节点就是最优方案——它正好覆盖了所有原有节点的位置。

构建完全二叉树

确定了目标大小 后，只需创建编号 到 的所有节点：

  • 若该编号在原树中存在，保留原始节点值。
  • 若不存在，新建值为 的节点。
  • 按 和 的关系连接父子。

样例演示

以输入 {1,#,1,1} 为例：

原树:          补全后:
   1              1
    \            / \
     1          1   1
    /          / \ /
   1          1  1 1
  • 根节点编号 ，右孩子编号 ，右孩子的左孩子编号 。
  • ，因此完全二叉树有 个节点（编号 到 ），对应输出 {1,1,1,1,1,1}。

复杂度

  • 时间复杂度：，其中 为原树节点在完全二叉树编号中的最大值。遍历原树 ，构建完全二叉树 。
  • 空间复杂度：，需要存储完全二叉树的所有节点。

代码

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int maxPos;
    unordered_map<int, int> valMap;

    void dfs(TreeNode* node, int pos) {
        if (!node) return;
        if (pos > maxPos) maxPos = pos;
        valMap[pos] = node->val;
        dfs(node->left, pos * 2);
        dfs(node->right, pos * 2 + 1);
    }

    TreeNode* build(int pos) {
        if (pos > maxPos) return nullptr;
        int v = valMap.count(pos) ? valMap[pos] : 1;
        TreeNode* node = new TreeNode(v);
        node->left = build(pos * 2);
        node->right = build(pos * 2 + 1);
        return node;
    }

    TreeNode* makeCompleteTree(TreeNode* root) {
        if (!root) return root;
        maxPos = 0;
        valMap.clear();
        dfs(root, 1);
        return build(1);
    }
};

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 {
    int maxPos;
    HashMap<Integer, Integer> valMap = new HashMap<>();

    void dfs(TreeNode node, int pos) {
        if (node == null) return;
        if (pos > maxPos) maxPos = pos;
        valMap.put(pos, node.val);
        dfs(node.left, pos * 2);
        dfs(node.right, pos * 2 + 1);
    }

    TreeNode build(int pos) {
        if (pos > maxPos) return null;
        int v = valMap.getOrDefault(pos, 1);
        TreeNode node = new TreeNode(v);
        node.left = build(pos * 2);
        node.right = build(pos * 2 + 1);
        return node;
    }

    public TreeNode makeCompleteTree(TreeNode root) {
        if (root == null) return root;
        maxPos = 0;
        valMap.clear();
        dfs(root, 1);
        return build(1);
    }
}

from collections import deque

class Solution:
    def makeCompleteTree(self, root):
        if not root:
            return root
        max_pos = 0
        val_map = {}
        q = deque()
        q.append((root, 1))
        while q:
            node, pos = q.popleft()
            if pos > max_pos:
                max_pos = pos
            val_map[pos] = node.val
            if node.left:
                q.append((node.left, pos * 2))
            if node.right:
                q.append((node.right, pos * 2 + 1))

        # 构建完全二叉树
        arr = [None] * (max_pos + 1)
        for i in range(1, max_pos + 1):
            arr[i] = TreeNode(val_map.get(i, 1))
        for i in range(1, max_pos + 1):
            left = i * 2
            right = i * 2 + 1
            if left <= max_pos:
                arr[i].left = arr[left]
            if right <= max_pos:
                arr[i].right = arr[right]
        return arr[1]

function makeCompleteTree(root) {
    if (!root) return root;
    let maxPos = 0;
    const valMap = new Map();
    const queue = [[root, 1]];
    let head = 0;
    while (head < queue.length) {
        const [node, pos] = queue[head++];
        if (pos > maxPos) maxPos = pos;
        valMap.set(pos, node.val);
        if (node.left) queue.push([node.left, pos * 2]);
        if (node.right) queue.push([node.right, pos * 2 + 1]);
    }

    // 构建完全二叉树
    const arr = new Array(maxPos + 1);
    for (let i = 1; i <= maxPos; i++) {
        arr[i] = new TreeNode(valMap.has(i) ? valMap.get(i) : 1);
    }
    for (let i = 1; i <= maxPos; i++) {
        const left = i * 2;
        const right = left + 1;
        if (left <= maxPos) arr[i].left = arr[left];
        if (right <= maxPos) arr[i].right = arr[right];
    }
    return arr[1];
}

module.exports = {
    makeCompleteTree: makeCompleteTree
};