先序遍历二叉树的递归算法
时间: 2023-11-14 17:27:57 浏览: 33
先序遍历二叉树的递归算法可描述为:
1. 如果二叉树为空,直接返回。
2. 访问根节点。
3. 对根节点的左子树进行先序遍历。
4. 对根节点的右子树进行先序遍历。
具体实现如下:
```c++
void preOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " "; // 访问根节点
preOrderTraversal(root->left); // 对左子树进行先序遍历
preOrderTraversal(root->right); // 对右子树进行先序遍历
}
```
其中,`TreeNode` 为二叉树的节点结构体,包含 `val`, `left` 和 `right` 三个成员变量,分别代表节点的值、左子节点和右子节点。
相关问题
二叉树先序遍历递归算法
二叉树先序遍历的递归算法如下:
1. 如果二叉树为空,则返回。
2. 访问根节点。
3. 对根节点的左子树进行先序遍历。
4. 对根节点的右子树进行先序遍历。
代码实现如下(假设二叉树的节点类型为Node):
```python
def preorder_traversal(root):
if root:
print(root.val) # 访问根节点
preorder_traversal(root.left) # 先序遍历左子树
preorder_traversal(root.right) # 先序遍历右子树
```
在上述代码中,我们首先判断了二叉树是否为空,如果不为空则依次执行访问根节点、先序遍历左子树、先序遍历右子树的操作。这样递归进行下去,直到遍历完整个二叉树。
递归方法先序遍历二叉树的算法思想
递归方法先序遍历二叉树的算法思想如下:
1. 如果二叉树为空,则返回。
2. 访问根节点。
3. 递归遍历左子树。
4. 递归遍历右子树。
具体实现可以参考以下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]:
res = []
def dfs(root):
if not root:
return
res.append(root.val)
dfs(root.left)
dfs(root.right)
dfs(root)
return res
```
其中,我们定义了一个TreeNode类来表示二叉树的节点,preorderTraversal函数用于实现先序遍历,dfs函数用于递归遍历二叉树。在dfs函数中,我们首先判断当前节点是否为空,如果为空则直接返回;否则,将当前节点的值加入结果列表中,然后递归遍历左子树和右子树。