在python中将二叉树按先序遍历存储到列表中,给出代码和注释
时间: 2024-05-25 15:19:31 浏览: 10
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
相关问题
用python代码给出将二叉树按先序遍历转化为链表的代码
以下是将二叉树按先序遍历转化为链表的Python代码:
```python
class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def flatten(self, root: Node) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root:
return
if root.left:
self.flatten(root.left)
if root.right:
self.flatten(root.right)
temp = root.right
root.right = root.left
root.left = None
while root.right:
root = root.right
root.right = temp
```
希望能对你有所帮助。
给定一棵二叉树的先序遍历序列和中序遍历序列python代码实现
以下是使用Python实现给定一棵二叉树的先序遍历序列和中序遍历序列的代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
root_index = inorder.index(root_val)
root.left = buildTree(preorder[1: 1+root_index], inorder[:root_index])
root.right = buildTree(preorder[1+root_index:], inorder[root_index+1:])
return root
```
这个函数的输入参数包括先序遍历序列和中序遍历序列,返回值是构建出的二叉树的根节点。在函数内部,首先检查先序遍历序列和中序遍历序列是否为空。如果有任何一个为空,则返回None。否则,我们可以确定根节点的值为先序遍历序列的第一个元素root_val。接下来,我们在中序遍历序列中找到root_val的索引位置root_index,为了构建二叉树,我们将中序遍历序列分成两半:inorder[:root_index]是左子树的中序遍历序列,inorder[root_index+1:]是右子树的中序遍历序列。对应地,通过切片操作,我们将先序遍历序列分为两个部分:preorder[1:1+root_index]是左子树的先序遍历序列,preorder[1+root_index:]是右子树的先序遍历序列。最后,我们递归地构建左子树和右子树,并将其分别赋值给根节点的left和right属性。整个过程结束后,我们返回根节点root。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)