按“先序”遍历存储表示的二叉树python
时间: 2023-09-15 16:20:38 浏览: 27
以下是按照先序遍历存储的二叉树的 Python 实现:
```python
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder):
if not preorder:
return None
val = preorder.pop(0)
if val is None:
return None
node = Node(val)
node.left = buildTree(preorder)
node.right = buildTree(preorder)
return node
```
假设先序遍历序列为 `preorder`,则可以通过 `buildTree(preorder)` 构建出该二叉树的根节点。其中,`preorder` 中的 None 表示空节点。
相关问题
输入二叉树的先序遍历,构建二叉树
可以按照以下步骤构建二叉树:
1. 建立一个栈,用于存储节点。
2. 从先序遍历中取出第一个数,作为根节点,并将其入栈。
3. 遍历先序遍历中的剩余数字,对于每一个数字:
- 如果该数字小于栈顶节点的值,将该数字作为栈顶节点的左子节点,并将其入栈。
- 如果该数字大于栈顶节点的值,将该数字作为栈顶节点的右子节点,并将其入栈。
- 如果该数字既不大于栈顶节点的值,也不小于栈顶节点的值,说明该数字不属于该子树,需要向上回溯,直到找到一个节点,该节点的值大于该数字,则将该数字作为该节点的右子节点,并将其入栈。
4. 完成遍历后,返回根节点即可。
以下是一段 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 = TreeNode(preorder[0])
stack = [root]
for val in preorder[1:]:
node = TreeNode(val)
if val < stack[-1].val:
stack[-1].left = node
else:
while stack and val > stack[-1].val:
parent = stack.pop()
parent.right = node
stack.append(node)
return root
```
其中,TreeNode 是二叉树的节点类,buildTree 函数接受先序遍历作为参数,并返回构建出的二叉树的根节点。
在python中将二叉树按先序遍历存储到列表中,给出代码和注释
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root: TreeNode) -> List[int]:
"""
将二叉树按先序遍历存储到列表中
:param root: 根节点
:return: 先序遍历结果列表
"""
if not root:
return []
res = [] # 存储先序遍历结果的列表
stack = [root] # 辅助栈,用于迭代遍历二叉树
while stack:
node = stack.pop() # 弹出栈顶元素
res.append(node.val) # 将当前节点的值加入到结果列表中
# 将右子节点入栈,这样在弹出栈顶元素时,右子节点会先被遍历到
if node.right:
stack.append(node.right)
# 将左子节点入栈,这样在弹出栈顶元素时,左子节点会后被遍历到
if node.left:
stack.append(node.left)
return res