按扩展二叉树的先序遍历结果构造二叉树的算法

构造二叉树的算法如下：

1. 创建一个栈stack，用于存储节点。
2. 从先序遍历的第一个元素开始，创建一个根节点root，并将其入栈。
3. 从先序遍历的第二个元素开始，遍历先序遍历中的所有元素：
- 如果当前元素是数字，创建一个新节点node，并将其作为根节点root的左子节点，将新节点node入栈。
- 如果当前元素是'#'，则表示该节点为null，将栈顶节点出栈，并将根节点root指向栈顶节点的右子节点。
4. 遍历完先序遍历中的所有元素后，返回根节点root。

例如，对于先序遍历序列"1 2 # # 3 # #"，构造的二叉树如下：

     1
    / \
   2   3

相关问题

二叉树先序遍历递归算法

二叉树先序遍历的递归算法如下：

1. 如果二叉树为空，则返回。
2. 访问根节点。
3. 对根节点的左子树进行先序遍历。
4. 对根节点的右子树进行先序遍历。

代码实现如下（假设二叉树的节点类型为Node）：

def preorder_traversal(root):
    if root:
        print(root.val) # 访问根节点
        preorder_traversal(root.left) # 先序遍历左子树
        preorder_traversal(root.right) # 先序遍历右子树

在上述代码中，我们首先判断了二叉树是否为空，如果不为空则依次执行访问根节点、先序遍历左子树、先序遍历右子树的操作。这样递归进行下去，直到遍历完整个二叉树。

编写求二叉树先序遍历的算法程序

以下是求二叉树先序遍历的算法程序（使用递归实现）：

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 = [root.val]
    res += preorderTraversal(root.left)
    res += preorderTraversal(root.right)
    return res

其中，`TreeNode` 是二叉树的节点类，包含值 `val`、左子树 `left`、右子树 `right`。`preorderTraversal` 函数接受根节点 `root`，返回一个列表，表示先序遍历结果。具体实现思路为：先访问根节点，再递归访问左子树和右子树。如果根节点为 `None`，直接返回空列表。