python链表先序遍历二叉树
时间: 2023-10-08 14:06:53 浏览: 69
下面是用Python实现二叉树的先序遍历:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
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
```
首先定义一个`TreeNode`类表示二叉树中的每个节点,包含一个值`val`和左右子节点`left`和`right`。然后,在`Solution`类中,定义一个`preorderTraversal`方法,接收根节点`root`作为参数,返回先序遍历的结果。
首先判断根节点是否为空,如果为空,则直接返回空列表。然后创建一个栈,将根节点入栈。当栈不为空时,弹出栈顶节点,将其值`val`加入结果列表中。然后,将其右子节点(如果有)和左子节点(如果有)依次入栈。重复上述操作,直到栈为空,最后返回结果列表即可。
注意,这里用的是迭代法实现先序遍历,还有递归法实现先序遍历,两种方法都可以。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)