leetcode - 105. Construct Binary Tree from Preorder and Inorder Traversal

**LeetCode105. Construct Binary Tree from Preorder and Inorder Traversal**

在本题中，我们需要根据前序遍历和中序遍历的结果，构造出一个二叉树。这个问题是经典的二叉树构造问题。

### 前序遍历前序遍历是一种从根节点开始，先访问根节点，然后再访问左子树和右子树的方式。例如，对于以下二叉树：

1 / 
23 /  
456

前序遍历的结果是：`[1,2,4,5,3,6]`。

### 中序遍历中序遍历是一种从左子树开始，先访问左子树，然后再访问根节点和右子树的方式。例如，对于以上二叉树：

1 / 
23 /  
456

中序遍历的结果是：`[4,2,5,1,3,6]`。

### 后续遍历后序遍历是一种从左子树开始，先访问左子树和右子树，然后再访问根节点的方式。例如，对于以上二叉树：

1 / 
23 /  
456

后序遍历的结果是：`[4,5,2,6,3,1]`。

### 构造二叉树现在，我们需要根据前序遍历和中序遍历的结果，构造出一个二叉树。我们可以使用以下方法：

* 如果前序遍历的第一个元素是根节点，那么我们就创建一个新的二叉树，并将其作为根节点。
* 然后，我们需要找到中序遍历中与根节点对应的左子树和右子树。我们可以通过在中序遍历中查找根节点来实现这一点。
* 一旦我们找到了左子树和右子树，我们就可以递归地构造出它们。

###代码示例

class TreeNode:
 def __init__(self, x):
 self.val = x self.left = None self.right = Nonedef buildTree(preorder, inorder):
 if not preorder or not inorder:
 return None root_val = preorder[0]
 root = TreeNode(root_val)
 idx = inorder.index(root_val)
 root.left = buildTree(preorder[1:idx+1], inorder[:idx])
 root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
 return rootdef printTree(root):
 if not root:
 return print(root.val, end=" ")
 if root.left:
 printTree(root.left)
 if root.right:
 printTree(root.right)

# 测试preorder = [1,2,4,5,3,6]
inorder = [4,2,5,1,3,6]

root = buildTree(preorder, inorder)
printTree(root) # 输出:124536

### 总结在本题中，我们需要根据前序遍历和中序遍历的结果，构造出一个二叉树。我们可以使用递归方法来实现这一点。首先，我们需要找到根节点，然后再递归地构造出左子树和右子树。最后，我们就可以得到整个二叉树。

### 注释* 在本题中，我们使用了递归方法来构造二叉树。这是因为二叉树的结构是递归的，即每个节点都有一个左子树和一个右子树。
* 我们需要找到根节点，然后再递归地构造出左子树和右子树。我们可以通过在中序遍历中查找根节点来实现这一点。
* 一旦我们找到了左子树和右子树，我们就可以递归地构造出它们。
* 最后，我们就可以得到整个二叉树。

### 相关问题* LeetCode106. Construct Binary Tree from Inorder and Postorder Traversal* LeetCode889. Construct a Binary Search Tree from a Given Preorder Traversal