二叉树的遍历-先序（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 preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.helper(root, res)
return res

def helper(self, root, res):
if not root:
return
res.append(root.val)
self.helper(root.left, res)
self.helper(root.right, res)

# 示例：
# root = [1,null,2,3]
# 输出：[1,2,3]

root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)

s = Solution()
print(s.preorderTraversal(root)) # [1, 2, 3]

相关问题

将一个完全二叉树的中序遍历转为先序遍历

要将一个完全二叉树的中序遍历转换为先序遍历，可以按照以下步骤进行操作：

1. 首先，我们需要了解先序遍历和中序遍历的特点：
- 先序遍历的顺序是：根节点 -> 左子树 -> 右子树。
- 中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

2. 对于一个完全二叉树来说，它的特点是：
- 左子树的节点编号是当前节点编号的两倍。
- 右子树的节点编号是当前节点编号的两倍加一。

3. 根据以上特点，我们可以通过递归的方式将中序遍历转换为先序遍历：
- 首先，找到中序遍历的第一个节点，即根节点。
- 然后，在中序遍历中找到根节点的位置，将其分为左子树和右子树。
- 接着，按照先序遍历的顺序，先输出根节点的值。
- 然后，递归地将左子树的中序遍历转换为先序遍历。
- 最后，递归地将右子树的中序遍历转换为先序遍历。

4. 以下是一个示例代码实现：

def inorder_to_preorder(inorder):
    if len(inorder) == 0:
        return []
    
    root = inorder[0]  # 根节点
    root_index = inorder.index(root)  # 根节点在中序遍历中的位置
    
    left_inorder = inorder[1:root_index]  # 左子树的中序遍历
    right_inorder = inorder[root_index+1:]  # 右子树的中序遍历
    
    left_preorder = inorder_to_preorder(left_inorder)  # 左子树的先序遍历
    right_preorder = inorder_to_preorder(right_inorder)  # 右子树的先序遍历
    
    return [root] + left_preorder + right_preorder  # 返回先序遍历结果

使用以上代码，我们可以将一个完全二叉树的中序遍历转换为先序遍历。

建立二叉树，并实现二叉树的遍历，先序遍历采用递归算法实现，层次遍历用非递归算法来实现。

好的，我来为您解答。首先，我们需要先了解二叉树的定义和遍历方式。

二叉树是一种树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树遍历包括先序遍历、中序遍历、后序遍历和层次遍历。

先序遍历：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

后序遍历：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。

层次遍历：从根节点开始，按照从上到下、从左到右的顺序依次访问每个节点。

接下来，我们来实现二叉树的建立和遍历。

# 定义节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 先序遍历（递归实现）
def preorderTraversal(root):
    if not root:
        return []
    res = [root.val]
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

# 层次遍历（非递归实现）
def levelOrderTraversal(root):
    if not root:
        return []
    res = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        res.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return res

# 测试代码
# 创建二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 先序遍历
print(preorderTraversal(root)) # [1, 2, 4, 5, 3]

# 层次遍历
print(levelOrderTraversal(root)) # [1, 2, 3, 4, 5]

以上就是二叉树的建立和遍历的实现代码。