递归实现二叉树节点与祖先最大差值：result返回问题求助

问题背景 #

我正在实现二叉树中节点与其祖先的最大差值计算，逻辑如下：

• 为每个节点找到左子树中的最小元素，记为res1
• 同理，找到右子树中的最小元素，记为res2
• 计算result为max(root-res1, root-res2)，并更新为目前找到的最大值

现有代码 #

import math

class Node:
    # global result
    result = -9999

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def max_diff(self, result):
        if self.left is None and self.right is None:
               return
        if self.left is not None:
               res1 = self.left.min_elem()  # find minimum in left subtree
        else:
             res1 = math.inf
        if self.right is not None:
                res2 = self.right.min_elem()  # find minimum in right subtree
        else:
             res2 = math.inf

        result = max(result, max(self.data - res1, self.data - res2))  # update result
        print(result)
        if self.left is not None:
                self.left.max_diff(result)
        if self.right is not None:
                self.right.max_diff(result)
        return

    def main_fn(self):
        self.max_diff(result)
        return result 

    def min_elem(self):
        # 补充实现寻找子树最小元素的方法
        min_val = self.data
        if self.left:
            min_val = min(min_val, self.left.min_elem())
        if self.right:
            min_val = min(min_val, self.right.min_elem())
        return min_val

class Tree:
    def __init__(self,root):
        self.root = root


node = Node(2)
node.left = Node(8)
node.left.left = Node(3)
node.left.right = Node(-2)
node.right = Node(0)
node.right.right=Node(5)

mytree = Tree(node)

resultnew= mytree.root.main_fn()

核心问题 #

原代码中result作为max_diff的参数传递，但Python的整数是不可变类型，递归调用中对result的修改不会影响外层的变量；同时main_fn里直接使用result未定义，导致报错，无法正确返回最终的最大差值。

解决方案 #

有两种可行的修改方式：

方式1：使用类实例属性存储result

把result改为Node类的实例属性，这样递归过程中可以直接修改并共享这个值：

import math

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.result = -9999  # 改为实例属性

    def max_diff(self):
        if self.left is None and self.right is None:
               return
        res1 = self.left.min_elem() if self.left else math.inf
        res2 = self.right.min_elem() if self.right else math.inf

        current_diff = max(self.data - res1, self.data - res2)
        if current_diff > self.result:
            self.result = current_diff
        
        if self.left:
            self.left.max_diff()
            # 同步子树的最大结果到当前节点
            if self.left.result > self.result:
                self.result = self.left.result
        if self.right:
            self.right.max_diff()
            if self.right.result > self.result:
                self.result = self.right.result

    def main_fn(self):
        self.max_diff()
        return self.result 

    def min_elem(self):
        min_val = self.data
        if self.left:
            min_val = min(min_val, self.left.min_elem())
        if self.right:
            min_val = min(min_val, self.right.min_elem())
        return min_val

class Tree:
    def __init__(self,root):
        self.root = root


node = Node(2)
node.left = Node(8)
node.left.left = Node(3)
node.left.right = Node(-2)
node.right = Node(0)
node.right.right=Node(5)

mytree = Tree(node)

resultnew= mytree.root.main_fn()
print(resultnew)  # 输出应为10（8 - (-2)）

方式2：让max_diff返回当前子树的最大差值

递归过程中，每个节点的max_diff返回当前子树能找到的最大差值，上层节点合并左右子树的结果：

import math

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

    def max_diff(self):
        current_max = -9999
        # 计算当前节点与左右子树最小值的差值
        res1 = self.left.min_elem() if self.left else math.inf
        res2 = self.right.min_elem() if self.right else math.inf
        current_diff = max(self.data - res1, self.data - res2)
        if current_diff > current_max:
            current_max = current_diff
        
        # 递归处理左右子树，获取子树的最大差值
        if self.left:
            left_max = self.left.max_diff()
            current_max = max(current_max, left_max)
        if self.right:
            right_max = self.right.max_diff()
            current_max = max(current_max, right_max)
        
        return current_max

    def main_fn(self):
        return self.max_diff()

    def min_elem(self):
        min_val = self.data
        if self.left:
            min_val = min(min_val, self.left.min_elem())
        if self.right:
            min_val = min(min_val, self.right.min_elem())
        return min_val

class Tree:
    def __init__(self,root):
        self.root = root


node = Node(2)
node.left = Node(8)
node.left.left = Node(3)
node.left.right = Node(-2)
node.right = Node(0)
node.right.right=Node(5)

mytree = Tree(node)

resultnew= mytree.root.main_fn()
print(resultnew)  # 输出应为10

说明 #

• 两种方式都解决了原代码中result传递无效的问题，方式1通过实例属性共享状态，方式2通过递归返回值传递结果。
• 补充了缺失的min_elem方法，这是原代码中未实现的关键逻辑。

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