2024-09-01
算法刷题
00

在这里插入图片描述

普通二叉树,每个节点的数值不相同。写一个函数,输入是树的根节点和要删除的节点的集合,删除某个节点意味着去除掉和这个节点的关联,剩下的都是子树,函数返回剩余子树数量。

input:root,{1}

output:2

input:root,{1,,2,5}

output:2

input:root,{1,,2}

output:3

input:root,{4}

output:3

input:root,{4,9}

output:2

程序还有点问题:

python
import copy from typing import Set class Node: def __init__(self, val): self.val = val self.left = None self.right = None def getSubTree(root: Node, elements: Set, node_del=False) -> int: """ if not elements or root is None: return 0 if root.val in elements: elements = copy.deepcopy(elements) elements.remove(root.val) left_num = 1 + getSubTree(root.left, elements, True) if root.left is not None else 0 right_num = 1 + getSubTree(root.right, elements, True) if root.right is not None else 0 if node_del: return left_num + right_num - 1 return left_num + right_num else: left_num = getSubTree(root.left, elements, False) if root.left is not None else 0 right_num = getSubTree(root.right, elements, False) if root.right is not None else 0 return left_num + right_num """ root = Node(1) root.left = tree2 = Node(2) root.right = tree3 = Node(3) tree2.left = tree4 = Node(4) tree2.right = tree5 = Node(5) tree3.left = tree6 = Node(6) tree3.right = tree7 = Node(7) tree4.left = tree8 = Node(8) tree4.right = tree9 = Node(9) print(getSubTree(root, {1, 2, 5}))
如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay

本文作者:Dong

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC。本作品采用《知识共享署名-非商业性使用 4.0 国际许可协议》进行许可。您可以在非商业用途下自由转载和修改,但必须注明出处并提供原作者链接。 许可协议。转载请注明出处!