普通二叉树,每个节点的数值不相同。写一个函数,输入是树的根节点和要删除的节点的集合,删除某个节点意味着去除掉和这个节点的关联,剩下的都是子树,函数返回剩余子树数量。
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
程序还有点问题:
pythonimport 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}))
本文作者:Dong
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC。本作品采用《知识共享署名-非商业性使用 4.0 国际许可协议》进行许可。您可以在非商业用途下自由转载和修改,但必须注明出处并提供原作者链接。 许可协议。转载请注明出处!