二叉树中序遍历的最优逻辑
时间: 2023-12-23 07:26:00 浏览: 83
先序遍历二叉树的算法
二叉树的中序遍历是指先遍历左子树,再遍历根节点,最后遍历右子树。其最优逻辑是使用递归实现,具体步骤如下:
1. 判断当前节点是否为空,如果为空则返回。
2. 递归遍历左子树。
3. 输出当前节点的值。
4. 递归遍历右子树。
下面是一个示例代码:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorderTraversal(root: TreeNode) -> List[int]:
res = []
def inorder(node):
if not node:
return
inorder(node.left)
res.append(node.val)
inorder(node.right)
inorder(root)
return res
```
其中,TreeNode是二叉树的节点类,inorderTraversal是中序遍历函数,root是二叉树的根节点。函数中使用了一个辅助函数inorder来实现递归遍历。在inorder函数中,先递归遍历左子树,再将当前节点的值加入结果列表,最后递归遍历右子树。最后返回结果列表即可。
阅读全文