二叉树的遍历!(简单) 二叉树作为FDS课程最核心的数据结构之一,要求每个人都掌握!
时间: 2024-01-14 15:01:54 浏览: 45
二叉树的遍历有三种方式:
1. 前序遍历(preorder traversal):先访问根节点,再访问左子树,最后访问右子树。
2. 中序遍历(inorder traversal):先访问左子树,再访问根节点,最后访问右子树。
3. 后序遍历(postorder traversal):先访问左子树,再访问右子树,最后访问根节点。
这三种遍历方式都可以使用递归或非递归的方式实现。其中,递归实现比较简单,非递归实现需要借助栈等数据结构来完成。
以下是前序遍历的递归实现代码:
```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 = []
if not root:
return res
res.append(root.val)
res += preorderTraversal(root.left)
res += preorderTraversal(root.right)
return res
```
以下是前序遍历的非递归实现代码:
```python
def preorderTraversal(root: TreeNode) -> List[int]:
res = []
stack = []
if not root:
return res
stack.append(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
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)