1080. 根到叶路径上的不足节点（Rating 1804）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1080. 根到叶路径上的不足节点

Rating 1804

思路

如果一个节点需要被删除，那么一定是其左右子树都遍历完后，发现所有路径上的节点和都小于limit。

而这件事情可以考虑使用递归的去做。

定义dfs函数，其返回某个节点的左右子节点都遍历完后的整条路径上的最大值。若这个最大值都小于limit，则这个节点就可以删掉。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:
        # 定义dfs
        # 输入是节点node，以及经过此节点前的路径和s
        # 输出是经过该节点的所有路径的最大路径和
        def dfs(node: Optional[TreeNode], s : int) -> int:
            if node.left: # 如果左树不为空
                left_val = dfs(node.left, s + node.val) # 向左dfs，更新 s 为 s + node.val
            if node.right: # 如果右树不为空
                right_val = dfs(node.right, s + node.val) # 向右dfs，更新 s 为 s + node.val

            if node.left and node.right: # 左右都不为空，则返回最大的值
                ret = max(left_val, right_val)
            elif node.left: # 只有左不为空，则返回左val
                ret = left_val
            elif node.right: # 只有右不为空，则返回右val
                ret = right_val
            else: # 都为空，即叶子节点，返回路径和即可
                ret = s + node.val

            if node.left and left_val < limit: # 判断左子树
                node.left = None
            if node.right and right_val < limit: # 判断右子树
                node.right = None
            return ret # 返回dfs答案

        if not root: # 本身树是空的情况下，返回空
            return root
        ret = dfs(root, 0)
        if ret < limit: # 最后要判断一下根节点，这块WA了一次
            return None
        return root

细节

在 Python 中，函数参数是通过引用传递的，但如果你直接传递一个对象（如TreeNode），你只能修改对象的属性，而不能改变对象本身的引用。

所以我们只能置node.left = None或者node.right = None，而不能直接node = None

例如以下代码，输出仍然为1，root.left并不会真的置为None

def test_del(node: Optional[TreeNode]):
    node = None

root = TreeNode(0)
root.left = TreeNode(1)
root.right = TreeNode(2)
test_del(root.left)
print(root.left.val)