创建二叉树、求二叉树的叶子节点、求二叉树的深度
时间: 2023-12-10 11:33:30 浏览: 85
以下是关于创建二叉树、求二叉树的叶子节点、求二叉树的深度的回答:
1. 创建二叉树
创建二叉树的方法有很多,这里提供一种基于Python的实现方法。我们可以定义一个二叉树节点类,然后通过递归的方式创建二叉树。
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def create_tree(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = create_tree(nums[:mid])
root.right = create_tree(nums[mid+1:])
return root
```
上述代码中,我们定义了一个TreeNode类,包含节点值val、左子节点left和右子节点right。create_tree函数接收一个列表nums作为参数,返回一个二叉树的根节点。在函数内部,我们首先判断nums是否为空,如果为空则返回None。否则,我们找到nums的中间位置mid,将mid位置的元素作为根节点的值,然后递归地创建左子树和右子树。
2. 求二叉树的叶子节点
二叉树的叶子节点是指没有子节点的节点。我们可以通过递归的方式遍历整个二叉树,统计叶子节点的个数。
```python
def count_leaves(root):
if not root:
return 0
if not root.left and not root.right:
return 1
return count_leaves(root.left) + count_leaves(root.right)
```
上述代码中,count_leaves函数接收一个二叉树的根节点root作为参数,返回二叉树的叶子节点个数。在函数内部,我们首先判断root是否为空,如果为空则返回0。然后判断root是否为叶子节点,如果是则返回1。否则,递归地计算左子树和右子树的叶子节点个数,并将它们相加。
3. 求二叉树的深度
二叉树的深度是指从根节点到最远叶子节点的最长路径上的节点数。我们可以通过递归的方式遍历整个二叉树,统计二叉树的深度。
```python
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return max(left_depth, right_depth) + 1
```
上述代码中,max_depth函数接收一个二叉树的根节点root作为参数,返回二叉树的深度。在函数内部,我们首先判断root是否为空,如果为空则返回0。然后递归地计算左子树和右子树的深度,并将它们的最大值加1返回。
阅读全文