先序遍历二叉树并将二叉树节点的值存储在列表总
时间: 2024-01-23 13:49:09 浏览: 25
体中,可以使用递归的方式实现,具体步骤如下:
1. 判断当前节点是否为空,如果为空则返回。
2. 将当前节点的值存储到列表中。
3. 递归遍历当前节点的左子树。
4. 递归遍历当前节点的右子树。
代码如下:
```
def preorderTraversal(root):
if not root:
return []
res = []
res.append(root.val)
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
```
其中,root为二叉树的根节点。在递归遍历左子树和右子树时,使用加法将结果合并到res列表中。最后返回res即可。
相关问题
先序遍历二叉树
先序遍历二叉树是指先遍历根节点,然后遍历左子树,最后遍历右子树。具体操作步骤如下:
1. 访问根节点
2. 先序遍历左子树
3. 先序遍历右子树
可以用递归或者栈来实现先序遍历。下面是一个使用递归的示例代码(假设二叉树的节点结构为TreeNode):
```python
def pre_order_traversal(root):
if not root:
return
print(root.val) # 访问根节点
pre_order_traversal(root.left) # 先序遍历左子树
pre_order_traversal(root.right) # 先序遍历右子树
```
如果使用栈来实现,可以按照以下步骤:
1. 将根节点入栈
2. 循环执行以下步骤直到栈为空:
1. 弹出栈顶元素并访问
2. 如果栈顶元素有右子树,将右子树入栈
3. 如果栈顶元素有左子树,将左子树入栈
下面是示例代码:
```python
def pre_order_traversal(root):
if not root:
return
stack = [root]
while stack:
node = stack.pop()
print(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
```
以上是先序遍历二叉树的两种实现方式。
python先序遍历二叉树
以下是Python实现二叉树先序遍历的代码示例:
```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]:
res = []
def preorder(root):
if not root:
return
res.append(root.val)
preorder(root.left)
preorder(root.right)
preorder(root)
return res
```
以上代码中,我们首先定义了一个二叉树节点类`TreeNode`,包含节点值`val`、左子节点`left`和右子节点`right`。然后定义了一个`preorderTraversal`函数,用于实现先序遍历二叉树。在函数中,我们定义了一个辅助函数`preorder`,用于递归遍历二叉树。具体实现中,我们先将当前节点的值加入结果列表`res`中,然后递归遍历左子树和右子树。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![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)