以二叉链表作为二叉树的存储结构,编写以下算法: (1)统计二叉树的叶结点个数。 (2)判别两棵树是否相等。 (8)输出二叉树中从每个叶子结点到根结点的路径
时间: 2024-02-13 20:01:08 浏览: 150
设二叉树采用链式存储结构,试设计一个算法计算一颗给定二叉树叶子节点的数目
5星 · 资源好评率100%
好的,我来逐个回答你的问题:
1. 统计二叉树的叶节点个数的算法如下:
```python
def count_leaf_nodes(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaf_nodes(root.left) + count_leaf_nodes(root.right)
```
2. 判别两棵树是否相等的算法如下:
```python
def is_same_tree(p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)
```
3. 输出二叉树中从每个叶子结点到根结点的路径的算法如下:
```python
def print_paths(root):
if not root:
return
path = []
print_paths_helper(root, path)
def print_paths_helper(node, path):
if not node:
return
path.append(node.val)
if not node.left and not node.right:
print(path[::-1])
else:
print_paths_helper(node.left, path)
print_paths_helper(node.right, path)
path.pop()
```
希望这些算法对你有所帮助!
阅读全文