Python实现,给定一颗二叉树先序遍历的输出结果,求出该树的中序遍历的
时间: 2024-05-10 17:13:44 浏览: 82
输出结果。
这个问题可以通过构建二叉树解决。先序遍历中,根节点是第一个遍历到的节点,因此可以将该节点作为二叉树的根节点。然后再根据中序遍历的特点,将左子树和右子树分别找出来,递归构建左右子树。最后得到的二叉树的中序遍历就是所求的输出结果。
下面是 Python 的代码实现:
```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
i = 1
while i < len(preorder) and preorder[i] < root_val:
i += 1
root.left = buildTree(preorder[1:i])
root.right = buildTree(preorder[i:])
return root
def inorderTraversal(root):
if not root:
return []
return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)
preorder = [5, 3, 1, 4, 7, 6, 8]
root = buildTree(preorder)
inorder = inorderTraversal(root)
print(inorder) #[1, 3, 4, 5, 6, 7, 8]
```
该代码通过 buildTree 函数构建出了给定的二叉树,并通过 inorderTraversal 函数遍历输出了中序遍历的结果。
阅读全文