首页利用先序遍历创建二叉树，返回指针

利用先序遍历创建二叉树，返回指针

时间: 2024-12-18 15:27:19 浏览: 39

利用先序遍历创建二叉树并返回根节点的操作通常涉及到递归的过程。先序遍历的顺序是“根-右”，即首先访问根节点，然后遍历左子树，最后遍历右子树。以下是Python中如何通过这种方法创建一个二叉树的示例： ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def buildTree(preorder): if not preorder: return None # 先序遍历的第一个元素是根节点 root_val = preorder[0] root = TreeNode(root_val) # 使用索引来查找根节点在后续元素中的位置 index = inorder.index(root_val) if inorder else None # 分别构建左右子树 if index + 1 < len(preorder): # 如果还有左子节点 root.left = buildTree(preorder[1:index+1]) if index < len(preorder) - 1: # 如果还有右子节点 root.right = buildTree(preorder[index+1:]) return root # 假设有一个先序遍历列表 pre = [1, 2, 4, 5, 3] 和中序遍历 inorder = [4, 2, 5, 1, 3] pre = [1, 2, 4, 5, 3] inorder = [4, 2, 5, 1, 3] root = buildTree(pre) ``` 在这个例子中，`buildTree`函数接收一个先序遍历列表作为输入，并基于该顺序构建出对应的二叉搜索树。

阅读全文