在含15个Employee节点的完全二叉树中应用动态规划的问题咨询

嘿，看起来你正在做一个挺有意思的需求——在15个节点的完全二叉树上用动态规划处理员工的评估分数，我来帮你把思路理清楚，同时完善代码结构和格式~

核心思路概述 #

针对这个场景，动态规划的核心是给每个节点维护两种状态：

• 选中当前节点：此时不能选择它的左右子节点，最大分数为当前节点分数 + 左右子节点不选中时的分数之和
• 不选中当前节点：此时可以自由选择左右子节点的最优状态，最大分数为左右子节点各自「选中/不选中」的最大值之和

因为是15个节点的完全二叉树（固定深度4，第4层有8个节点），DFS遍历就能覆盖所有节点，不需要额外处理结构适配问题。

完整代码实现 #

首先补充你没提到的基础类定义，再完善BT类的动态规划逻辑：

1. Employee类定义 #

class Employee {
    double Evaluation_Score;
    int ID;

    public Employee(int id, double score) {
        this.ID = id;
        this.Evaluation_Score = score;
    }
}

2. 二叉树节点类定义 #

class BTNode<T> {
    T data;
    BTNode<T> left, right;

    public BTNode(T data) {
        this.data = data;
        this.left = this.right = null;
    }
}

3. 带动态规划逻辑的BT类 #

import java.util.HashMap;
import java.util.Map;

public class BT<T> {
    BTNode<T> root, current;

    public BT() {
        root = current = null;
    }

    // 根据ID查找目标节点
    public BTNode<Employee> find(int targetId) {
        return searchNode((BTNode<Employee>) root, targetId);
    }

    private BTNode<Employee> searchNode(BTNode<Employee> node, int targetId) {
        if (node == null) return null;
        if (node.data.ID == targetId) return node;
        
        BTNode<Employee> leftResult = searchNode(node.left, targetId);
        if (leftResult != null) return leftResult;
        return searchNode(node.right, targetId);
    }

    // 计算最大评估分数组合值
    public double max() {
        // 用Map存储每个节点的两种状态值，避免重复计算
        Map<BTNode<Employee>, Double> selected = new HashMap<>();
        Map<BTNode<Employee>, Double> notSelected = new HashMap<>();
        
        dfs((BTNode<Employee>) root, selected, notSelected);
        return Math.max(
            selected.getOrDefault(root, 0.0),
            notSelected.getOrDefault(root, 0.0)
        );
    }

    // 深度优先遍历填充状态
    private void dfs(BTNode<Employee> node, 
                     Map<BTNode<Employee>, Double> selected, 
                     Map<BTNode<Employee>, Double> notSelected) {
        if (node == null) return;

        // 先递归处理左右子节点
        dfs(node.left, selected, notSelected);
        dfs(node.right, selected, notSelected);

        // 计算选中当前节点的最大分数
        double selectScore = node.data.Evaluation_Score;
        if (node.left != null) {
            selectScore += notSelected.getOrDefault(node.left, 0.0);
        }
        if (node.right != null) {
            selectScore += notSelected.getOrDefault(node.right, 0.0);
        }
        selected.put(node, selectScore);

        // 计算不选中当前节点的最大分数
        double notSelectScore = 0;
        if (node.left != null) {
            notSelectScore += Math.max(
                selected.getOrDefault(node.left, 0.0),
                notSelected.getOrDefault(node.left, 0.0)
            );
        }
        if (node.right != null) {
            notSelectScore += Math.max(
                selected.getOrDefault(node.right, 0.0),
                notSelected.getOrDefault(node.right, 0.0)
            );
        }
        notSelected.put(node, notSelectScore);
    }
}

关键细节说明 #

• 状态记忆化：用两个Map存储节点状态，避免重复计算子树的最优值，时间复杂度为O(n)（n为节点数）
• find方法优化：递归查找在15节点的完全二叉树中足够高效，如果需要更快的查找，可以利用完全二叉树的数组特性（节点i的左子节点为2i+1，右子节点为2i+2），直接用数组存储节点实现O(1)查找
• 完全二叉树适配：DFS遍历会自动覆盖所有节点，不需要针对完全二叉树做特殊处理

使用示例 #

public class Main {
    public static void main(String[] args) {
        BT<Employee> tree = new BT<>();
        // 构建15个节点的完全二叉树（示例ID从1到15，分数自定义）
        BTNode<Employee> root = new BTNode<>(new Employee(1, 8.5));
        root.left = new BTNode<>(new Employee(2, 9.0));
        root.right = new BTNode<>(new Employee(3, 7.8));
        // 继续构建剩余12个节点...
        tree.root = root;

        // 计算最大分数组合
        double maxScore = tree.max();
        System.out.println("最大评估分数组合值：" + maxScore);

        // 根据ID查找节点
        BTNode<Employee> targetNode = tree.find(5);
        if (targetNode != null) {
            System.out.println("ID为5的员工评估分数：" + targetNode.data.Evaluation_Score);
        }
    }
}

内容的提问来源于stack exchange，提问作者user7150641