不相邻节点的最大和

2026-02-14 03:35:42 0条评论 1次阅读 0人点赞

在算法与数据结构的学习与工程实践中，二叉树的问题总是我们绕不开的关卡。给定一个包含整数值的二叉树的根节点，我们面临的一个经典挑战是：找出满足特定条件的节点值的最大和——即在求和中不能包含通过边直接相连的两个节点。这个问题的解法不仅展示了递归与动态规划的优雅结合，更是在我们处理资源调度、权限控制等实际业务场景时的核心逻辑。

示例分析：

在第一个示例中，我们看到输出为 11。这是通过直接选取节点 11 得到的。而在第二个更复杂的例子中，最大和为 27。这并不是简单地把所有正数加起来，而是通过组合节点 15 和节点 12 得到的。这两个节点在树结构中并不相邻，因此符合我们的约束条件。这种“包含-排除”的二元选择思想，贯穿了我们今天要讨论的所有解决方案。

朴素方法：使用递归

当我们第一次面对这个问题时，最直观的思路往往是利用递归。我们可以通过这样一个事实来解决问题：一个节点和它的直接子节点不能同时包含在求和中。

这促使我们为每个节点定义两种策略：

  • 将当前节点的值包含在总和中：在这种情况下，我们不能将其直接子节点的值包含在总和中。因此，我们需要递归地对当前节点的孙节点（即左孩子的左右孩子和右孩子的左右孩子）调用函数。
  • 将当前节点的值排除在总和外：在这种情况下，我们可以自由选择将其直接子节点的值包含在总和中。因此，我们递归地对当前节点的直接子节点调用函数。

最后，我们将从这两种结果中选择最大值作为最终结果。虽然这种方法逻辑清晰，但它的时间复杂度较高，因为存在大量的重复计算。但在我们探索原型或处理小规模数据时，它依然是首选。

#include 
#include 
using namespace std;

// Node Structure
class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int x) {
        data = x;
        left = right = NULL;
    }
};

// method to return the maximum 
// sum rooted at the node ‘node‘
int getMaxSumUtil(Node* node) {
    if (node == NULL) return 0;

    // Strategy 1: Include the current node
    int includeNode = node->data;

    if (node->left != NULL) {
        includeNode += getMaxSumUtil(node->left->left) +
                       getMaxSumUtil(node->left->right);
    }

    if (node->right != NULL) {
        includeNode += getMaxSumUtil(node->right->left) +
                       getMaxSumUtil(node->right->right);
    }

    // Strategy 2: Exclude the current node
    int excludeNode = getMaxSumUtil(node->left) + 
                      getMaxSumUtil(node->right);

    // The result for the current node is the
    // maximum of including or excluding it
    return max(includeNode, excludeNode);
}

int getMaxSum(Node* root) {
    if (root == NULL) return 0;
    return getMaxSumUtil(root);
}

int main() {
    // Create binary tree as shown in examples
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->right->left = new Node(4);
    root->right->right = new Node(5);
    root->left->left = new Node(1);

    cout << "Maximum Sum: " << getMaxSum(root) << endl;
    return 0;
}

// Node Structure
class Node {
    int data;
    Node left, right;
    
    Node(int x) {
        data = x;
        left = right = null;
    }
}

class GFG {
    // method to return the maximum 
    // sum rooted at the node ‘node‘
    static int getMaxSumUtil(Node node) {
        if (node == null) return 0;
        
        int includeNode = node.data;
        
        if (node.left != null) {
            includeNode += getMaxSumUtil(node.left.left) + 
                           getMaxSumUtil(node.left.right);
        }
        
        if (node.right != null) {
            includeNode += getMaxSumUtil(node.right.left) + 
                           getMaxSumUtil(node.right.right);
        }

        int excludeNode = getMaxSumUtil(node.left) + 
                          getMaxSumUtil(node.right);

        return Math.max(includeNode, excludeNode);
    }

    static int getMaxSum(Node root) {
        if (root == null) return 0;
        return getMaxSumUtil(root);
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(4);
        root.right.right = new Node(5);
        root.left.left = new Node(1);

        System.out.println(getMaxSum(root));
    }
}

# Python Node Definition
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def getMaxSumUtil(node):
    if node is None:
        return 0

    # Include current node
    include = node.data
    if node.left:
        include += getMaxSumUtil(node.left.left) + getMaxSumUtil(node.left.right)
    if node.right:
        include += getMaxSumUtil(node.right.left) + getMaxSumUtil(node.right.right)

    # Exclude current node
    exclude = getMaxSumUtil(node.left) + getMaxSumUtil(node.right)

    return max(include, exclude)

def getMaxSum(root):
    if root is None:
        return 0
    return getMaxSumUtil(root)

推荐方法：使用包含-排除策略（Pair 返回法）

虽然上述递归方法可行，但你会发现，对于树中相同的节点，我们的代码会多次计算相同的子问题。这导致了指数级的时间复杂度。作为一个经验丰富的开发者，我们深知这种代码在生产环境中是不可接受的，尤其是当树的深度增加时，它会导致栈溢出或超时。

为了优化这一点，我们引入了包含-排除策略的进阶版。我们不再每次只返回一个整数，而是返回一个对，表示“包含当前节点时的最大和”与“不包含当前节点时的最大和”。

这种做法本质上是动态规划思想在树形结构上的应用（自底向上的 DP）。我们定义一个辅助结构 pair，它存储两个值：

  • first: 当前节点被包含时的最大和。
  • second: 当前节点被排除时的最大和。

计算逻辑非常清晰：

  • 包含当前节点：我们必须排除其左右子节点。所以，res.first = node.data + left.second + right.second。
  • 排除当前节点：我们可以自由选择其子节点是包含还是排除（取最大值）。所以，res.second = max(left.first, left.second) + max(right.first, right.second)。

这种方法将时间复杂度降低到了 O(n)，因为我们只访问每个节点一次。同时，空间复杂度也优化到了 O(h)，其中 h 是树的高度（主要用于递归栈）。

#include 
using namespace std;

// Node Structure
class Node {
public:
    int data;
    Node *left, *right;
    Node(int x) : data(x), left(NULL), right(NULL) {}
};

// Pair to store the two states
class Pair {
public:
    int incl;  // Max sum including the current node
    int excl;  // Max sum excluding the current node
};

// Helper function that returns the Pair
Pair getMaxSumHelper(Node* root) {
    Pair p;
    
    // Base case: An empty node contributes 0 to both states
    if (root == NULL) {
        p.incl = 0;
        p.excl = 0;
        return p;
    }

    // Recursively get pairs for left and right subtrees
    Pair left = getMaxSumHelper(root->left);
    Pair right = getMaxSumHelper(root->right);

    // Logic: 
    // If we include the current node, we cannot include its children.
    // So we add the ‘excl‘ values of children to current data.
    p.incl = root->data + left.excl + right.excl;

    // If we exclude the current node, we can choose to include or exclude children.
    // So we take the maximum of ‘incl‘ and ‘excl‘ for both children and sum them.
    p.excl = max(left.incl, left.excl) + max(right.incl, right.excl);

    return p;
}

int getMaxSum(Node* root) {
    Pair res = getMaxSumHelper(root);
    // The final result is the maximum of including or excluding the root
    return max(res.incl, res.excl);
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->right->left = new Node(4);
    root->right->right = new Node(5);
    root->left->left = new Node(1);

    cout << "Maximum Sum: " << getMaxSum(root) << endl;
    return 0;
}

现代开发范式与 2026 前沿视角

在我们深入探讨了底层算法之后，让我们跳出纯粹的代码逻辑，站在 2026 年的技术高度，看看我们在实际工程中如何运用这些知识。

#### 1. AI 辅助工作流与 Vibe Coding（氛围编程）

在当下，尤其是到了 2026 年，我们编写代码的方式已经发生了根本性的变化。你可能已经习惯了使用 Cursor 或 Windsurf 这样的 AI 原生 IDE。当我们在面试中或者解决 LeetCode 困难题时，我们不再孤独地面对白板。

利用 Agentic AI（自主智能体），我们可以将算法问题直接转化为文档、测试用例甚至可视化图表。例如，当我们处理“非相邻节点最大和”这类问题时，我们会利用 AI 辅助工具生成树的可视化结构，这比单纯在脑海中构建要直观得多。这种“氛围编程”不仅仅是补全代码，更是一种与我们协作探索解决方案的伙伴关系。AI 可以帮助我们识别上述朴素递归中的重复计算风险，并建议我们使用 Pair 结构来优化，这大大提升了我们的开发效率。

#### 2. 生产级代码的容灾与边界情况

让我们思考一下：如果在生产环境中运行这段代码，哪里可能会出错？

我们在编写 getMaxSum 时，考虑了节点为空的情况，这是基本的防御性编程。但在分布式系统或云原生环境中，数据源可能是不稳定的。

  • 数据完整性：如果树结构是通过网络传输的 JSON 构建的，我们可能会遇到循环引用（尽管二叉树通常不应该有）。在实际代码中，我们需要添加检测循环的机制，或者限制递归深度以防止堆栈溢出（Stack Overflow）。
  • 内存管理：在 C++ 中，我们使用了 INLINECODE92ed9a45 分配内存。在一个长期运行的服务中，如果树的创建和销毁非常频繁，我们需要考虑使用智能指针（如 INLINECODEaad5766c 或 std::unique_ptr）来自动管理内存，防止内存泄漏。
  • 性能监控：使用现代的可观测性工具，我们可以为这个算法添加 Tracing（链路追踪）。如果这个求和操作被用于实时交易风控系统，延迟必须在毫秒级。我们会记录自顶向下递归和自底向上 DP 的耗时差异，确保我们的优化真正产生了业务价值。

#### 3. 技术选型：从算法到架构的延伸

最后，让我们讨论一下这个问题的实际应用场景。这个问题通常被称为“House Robber”（打家劫舍）问题的树形版本。在 2026 年，随着物联网和边缘计算的发展，这种算法逻辑常用于：

  • 边缘计算资源调度：在传感器网络中，如果两个相邻的传感器同时工作会产生信号干扰，我们可以在树状拓扑网络中利用此算法计算最大数据吞吐量，同时不激活相邻的节点。
  • 权限控制：在组织架构树中，如果我们要审批流程，且上下级不能同时审批（防欺诈），我们就可以使用这个逻辑来选择最佳审批路径。

总结：

从朴素递归到动态规划的优化，展示了我们对计算复杂度的掌控。而在 2026 年的工程实践中，我们不仅要写出 O(n) 的算法，更要懂得如何利用 AI 工具加速开发，如何考虑边缘情况和长期维护。希望这篇文章能帮助你更全面地理解这个经典问题及其背后的工程思维。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/47772.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年