Python中删除二叉树中只有一个子节点的所有节点?
假设我们有一个二叉树根节点,我们需要删除所有只有一个子节点的节点。
因此,如果输入如下:
则输出将是
为了解决这个问题,我们将遵循以下步骤:
- 定义一个名为solve()的方法,它将采取树根
-
如果root为空,则
- 返回root
- 如果root的左侧为空且root的右侧为空,则
- 返回root
- 如果root的左侧为空,则
- 返回solve(root的右侧)
- 如果root的右侧为空,则
- 返回solve(root的左侧)
- root的左侧:= solve(root的左侧)
-
root的右侧:= solve(root的右侧)
-
返回root
更多Python相关文章,请阅读:Python 教程
示例
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.data, end = ', ')
print_tree(root.right)
class Solution:
def solve(self, root):
if not root:
return root
if not root.left and not root.right:
return root
if not root.left:
return self.solve(root.right)
if not root.right:
return self.solve(root.left)
root.left = self.solve(root.left)
root.right = self.solve(root.right)
return root
ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.right = TreeNode(5)
root.left.left.right = TreeNode(6)
root.right.right.left = TreeNode(7)
root.right.right.right = TreeNode(8)
res = ob.solve(root)
print_tree(res)
输入
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.right = TreeNode(5)
root.left.left.right = TreeNode(6)
root.right.right.left = TreeNode(7)
root.right.right.right = TreeNode(8)
输出
6, 1, 7, 5, 8,