代码实现二叉树的以下功能:二叉树的创建、二叉树的三种递归遍历、二叉树的复制、统计二叉树的结点数,统计二叉树叶子节点数、计算二叉树的深度、交换二叉树每个结点的左孩和右孩。
时间: 2023-12-01 14:40:51 浏览: 77
二叉树功能的实现代码
以下是二叉树的相关功能实现:
1. 二叉树的创建
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def create_tree(lst):
if not lst:
return None
mid = len(lst) // 2
root = TreeNode(lst[mid])
root.left = create_tree(lst[:mid])
root.right = create_tree(lst[mid+1:])
return root
```
2. 二叉树的三种递归遍历
```python
def preorder_traversal(root):
if not root:
return []
res = [root.val]
res += preorder_traversal(root.left)
res += preorder_traversal(root.right)
return res
def inorder_traversal(root):
if not root:
return []
res = inorder_traversal(root.left)
res += [root.val]
res += inorder_traversal(root.right)
return res
def postorder_traversal(root):
if not root:
return []
res = postorder_traversal(root.left)
res += postorder_traversal(root.right)
res += [root.val]
return res
```
3. 二叉树的复制
```python
def copy_tree(root):
if not root:
return None
new_root = TreeNode(root.val)
new_root.left = copy_tree(root.left)
new_root.right = copy_tree(root.right)
return new_root
```
4. 统计二叉树的结点数
```python
def count_nodes(root):
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
```
5. 统计二叉树叶子节点数
```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)
```
6. 计算二叉树的深度
```python
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
```
7. 交换二叉树每个结点的左孩和右孩
```python
def swap_left_right(root):
if not root:
return None
root.left, root.right = root.right, root.left
swap_left_right(root.left)
swap_left_right(root.right)
return root
```
阅读全文