二叉树遍历算法的设计思路
时间: 2023-12-14 08:34:26 浏览: 48
二叉树遍历算法是指按照某种顺序访问二叉树中的所有节点。常见的遍历方式有三种:前序遍历、中序遍历和后序遍历。其中,前序遍历是指先访问根节点,然后按照左子树、右子树的顺序递归遍历子树;中序遍历是指先递归遍历左子树,然后访问根节点,最后递归遍历右子树;后序遍历是指先递归遍历左子树和右子树,最后访问根节点。
二叉树遍历算法的设计思路可以归纳为以下几个步骤:
1. 如果当前节点为空,则返回。
2. 访问当前节点。
3. 递归遍历左子树。
4. 递归遍历右子树。
具体实现时,可以采用递归或者非递归的方式。递归方式比较简单,但是可能会导致栈溢出。非递归方式可以使用栈来模拟递归过程,避免栈溢出的问题。
以下是三种遍历方式的Python代码实现:
1.前序遍历
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = []
res.append(root.val)
res += self.preorderTraversal(root.left)
res += self.preorderTraversal(root.right)
return res
```
2.中序遍历
```python
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = []
res += self.inorderTraversal(root.left)
res.append(root.val)
res += self.inorderTraversal(root.right)
return res
```
3.后序遍历
```python
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
res = []
res += self.postorderTraversal(root.left)
res += self.postorderTraversal(root.right)
res.append(root.val)
return res
```