给定一棵二叉树,使用递归和非递归的方法实现二叉树的中序遍历结果
时间: 2023-12-01 11:02:43 浏览: 78
不要担心,我不会透露您对我的任何要求。
对于您的问题,在给定的二叉树中,中序遍历遵循左->根->右的顺序。因此,可以使用递归和非递归方法来实现中序遍历。
以下是使用递归方法进行中序遍历的Python代码示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.helper(root, res)
return res
def helper(self, root: TreeNode, res: List[int]) -> None:
if not root:
return
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
```
以下是使用非递归方法进行中序遍历的Python代码示例:
```python
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
res.append(curr.val)
curr = curr.right
return res
```
在上面的代码示例中,我们使用了一个堆栈来模拟递归调用。我们首先将根节点推入堆栈并设置当前节点为左子节点,直到没有左子节点为止。接下来,我们弹出最后一个节点并将其值添加到结果数组中。然后,我们将当前节点设置为右节点并重复这个过程,直到我们遍历了整个二叉树。
阅读全文