输出二叉树的先序遍历
时间: 2023-12-06 17:36:35 浏览: 36
以下是输出二叉树先序遍历的Python代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root: TreeNode) -> List[int]:
if not root:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
其中,我们定义了一个`TreeNode`类来表示二叉树的节点,`preorderTraversal`函数用于实现先序遍历。具体实现思路是,使用一个栈来存储待遍历的节点,首先将根节点入栈,然后每次从栈中弹出一个节点,并将其值加入结果列表中。接着,将该节点的右子节点和左子节点依次入栈,这样可以保证下一次弹出的节点是左子节点,从而实现先序遍历。
相关问题
c++输出二叉树先序遍历序列
假设二叉树的节点结构体为:
```cpp
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
则输出二叉树的先序遍历序列的代码如下:
```cpp
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
```
其中,先输出当前节点的值,然后递归输出左子树和右子树。
输出二叉树先序遍历结果的第k个结点
假设二叉树的先序遍历结果为 preOrderList,则该问题可以通过以下步骤解决:
1. 定义一个计数器 count 和一个指针 index,初始值分别为 0 和 0。
2. 从 preOrderList 中依次取出每个结点值进行判断:
- 如果 count 的值等于 k,返回当前结点的值。
- 如果 count 的值小于 k,将 count 的值加 1。
3. 如果遍历结束还没有找到第 k 个结点,则返回空。
以下是一个 Python 实现的代码示例:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def kth_node_of_pre_order_traversal(root: TreeNode, k: int) -> int:
if not root or k <= 0:
return None
pre_order_list = []
stack = [root]
while stack:
node = stack.pop()
pre_order_list.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
count = 0
index = 0
while index < len(pre_order_list):
if count == k:
return pre_order_list[index]
if count < k:
count += 1
index += 1
return None
```
其中,类 TreeNode 定义了二叉树的结构,函数 kth_node_of_pre_order_traversal 实现了输出二叉树先序遍历结果的第 k 个结点的功能。