二叉树层次遍历pta
时间: 2024-01-07 12:21:40 浏览: 33
以下是二叉树层次遍历的Python实现,其中使用了队列来实现层次遍历:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
queue = [root]
while queue:
level = []
for i in range(len(queue)):
node = queue.pop(0)
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
```
其中,TreeNode类表示二叉树的节点,levelOrder函数实现了二叉树的层次遍历,返回一个列表,其中每个元素表示一层的节点值。
相关问题
二叉树中序遍历java
以下是二叉树中序遍历的Java代码实现:
递归法:
```java
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
private void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
}
```
迭代法:
```java
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>(); Deque<TreeNode> stack = new LinkedList<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}
```
二叉树中序遍历非递归
二叉树中序遍历非递归算法可以使用栈来实现。具体实现方法如下:
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;
}
```