在Python中找出二叉树中唯一子节点的节点数
假设我们有一棵二叉树,我们需要找出只有一个子节点的节点数。我们知道,当一个节点x的父节点恰好有一个是x的子节点时,节点x是唯一子节点。
因此,如果输入如下图所示:
则输出将为2,因为8和6是唯一的子节点。
为了解决这个问题,我们将按照以下步骤执行:
- 如果根节点为空,那么
- 返回0
- d:一个双向队列
- 将根插入到d的末尾
- 计数:0
- 当d不为空时,执行以下操作
- current:d的左侧元素并删除左侧元素
- 如果当前节点的左侧不为空,则
- 将当前节点的左侧插入到d中
- 如果当前节点的右侧为空,则
- count:count + 1
- 如果当前节点的右侧不为空,则
- 将当前节点的右侧插入到d中
- 如果当前节点的左侧为空,则
- count:count + 1
- 返回计数
让我们看下面的实现以更好地理解:
更多Python相关文章,请阅读:Python 教程
示例代码
from collections import deque
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
if not root:
return 0
d = deque()
d.append(root)
count = 0
while d:
current = d.popleft()
if current.left:
d.append(current.left)
if not current.right:
count += 1
if current.right:
d.append(current.right)
if not current.left:
count += 1
return count
ob = Solution()
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.right = TreeNode(8)
root.right.right = TreeNode(6)
print(ob.solve(root))
输入
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.right = TreeNode(8)
root.right.right = TreeNode(6)
输出
2