建立二叉树,并实现二叉树的遍历以及求根结点到指定结点的路径。
时间: 2024-03-06 11:50:01 浏览: 26
好的,我可以帮助你解决这个问题。
二叉树的遍历有三种方式:先序遍历、中序遍历和后序遍历。其中,先序遍历的顺序是先访问根节点,然后访问左子树,最后访问右子树;中序遍历的顺序是先访问左子树,然后访问根节点,最后访问右子树;后序遍历的顺序是先访问左子树,然后访问右子树,最后访问根节点。
以下是建立二叉树并实现遍历的代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
# 先序遍历
def preorder_traversal(root):
if root:
print(root.val, end=" ")
preorder_traversal(root.left)
preorder_traversal(root.right)
# 中序遍历
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val, end=" ")
inorder_traversal(root.right)
# 后序遍历
def postorder_traversal(root):
if root:
postorder_traversal(root.left)
postorder_traversal(root.right)
print(root.val, end=" ")
# 构建二叉树
def build_tree(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = build_tree(nums[:mid])
root.right = build_tree(nums[mid+1:])
return root
# 求根结点到指定结点的路径
def find_path(root, target, path):
if not root:
return False
path.append(root.val)
if root.val == target:
return True
if (root.left and find_path(root.left, target, path)) or (root.right and find_path(root.right, target, path)):
return True
path.pop()
return False
# 测试样例
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
root = build_tree(nums)
preorder_traversal(root) # 5 2 1 4 3 7 6 9 8
print("")
inorder_traversal(root) # 1 2 3 4 5 6 7 8 9
print("")
postorder_traversal(root) # 1 3 4 2 6 8 9 7 5
print("")
path = []
find_path(root, 8, path)
print(path) # [5, 7, 8]
```
以上代码中,`TreeNode` 表示二叉树的结点,包含结点值 `val` 和左右子节点 `left` 和 `right`。`build_tree` 函数用来构建二叉树,采用分治法的思想,将数组从中间分为左右两部分,左半部分构建左子树,右半部分构建右子树,递归执行即可。`preorder_traversal`、`inorder_traversal` 和 `postorder_traversal` 分别代表先序遍历、中序遍历和后序遍历,这里采用递归的方式实现。`find_path` 函数用来求根结点到指定结点的路径,如果找到了目标结点,就返回 `True`,并将路径存储在 `path` 列表中,否则返回 `False`。