递归完成二叉树的中序遍历
时间: 2023-11-14 19:20:47 浏览: 14
二叉树的中序遍历是先遍历左子树,再遍历根节点,最后遍历右子树。递归实现如下:
```
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 = []
inorder(root, res)
return res
def inorder(root, res):
if root:
inorder(root.left, res)
res.append(root.val)
inorder(root.right, res)
```
首先,定义一个辅助函数 inorder,该函数用于实现中序遍历。如果当前节点存在,则先遍历左子树,再将当前节点的值加入结果列表中,最后遍历右子树。
主函数 inorderTraversal 调用辅助函数 inorder,并将结果列表返回。
相关问题
二叉树中序遍历非递归
### 回答1:
二叉树的中序遍历非递归实现需要借助栈来实现。具体步骤如下:
1. 首先将根节点入栈;
2. 当栈不为空时,取出栈顶节点,如果该节点有左子树,则将其左子树入栈;
3. 如果该节点没有左子树,则访问该节点,并将其右子树入栈;
4. 重复步骤2和步骤3,直到栈为空。
下面是Java代码实现:
```java
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
}
return res;
}
```
其中,TreeNode是二叉树的节点类,val表示节点值,left和right表示左右子节点。
### 回答2:
二叉树的中序遍历是指按照左子树、根节点、右子树的顺序遍历二叉树。通常,我们使用递归算法来实现二叉树的遍历操作。然而,递归算法利用了系统的函数调用栈,当二叉树的高度非常大时,递归可能会导致栈溢出的问题。因此,我们需要考虑使用非递归的方式来实现二叉树的中序遍历。
以下是一种基于栈的非递归中序遍历的思路:
1. 首先,创建一个栈和一个指针指向二叉树的根节点。
2. 如果指针不为空或者栈不为空,则继续遍历二叉树。
3. 当指针不为空时,将指针指向的节点压入栈中,并将指针指向其左子节点。
4. 当指针为空时,说明左子树已经遍历完毕,此时从栈中弹出一个节点并访问它,并将指针指向其右子节点。
5. 重复步骤3和4,直到指针为空且栈为空。
通过以上步骤,我们可以按照中序遍历的顺序遍历整个二叉树,且不使用递归算法。在每次遍历时,会将当前节点的左子节点全部入栈,然后再访问栈顶节点、访问右子节点。通过栈的结构,能够保持遍历顺序并避免出现栈溢出的问题。
这种非递归的中序遍历实现方式具有较好的效率和空间利用率,适用于各种规模的二叉树的遍历。
二叉树中序遍历非递归
二叉树中序遍历非递归算法可以使用栈来实现。具体实现方法如下:
1. 定义一个栈和一个指向根节点的指针。
2. 将根节点和它的所有左子树全部入栈。
3. 当栈不为空时,取出栈顶元素,将其值存入结果数组中。
4. 如果该节点有右子树,则将右子树及其所有左子树全部入栈。
5. 重复步骤3和4,直到栈为空。
代码实现如下(C++):
```
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> st;
TreeNode* p = root;
while (p != NULL || !st.empty()) {
while (p != NULL) {
st.push(p);
p = p->left;
}
p = st.top();
st.pop();
res.push_back(p->val);
p = p->right; }
return res;
}
```