gpt-3.5-turbo-0301· openai
Suzhen/CodeChat
重构二叉树:先序遍历CBEGDFA,后序遍历CGEFDBA
- User
重构二叉树:先序遍历CBEGDFA,后序遍历CGEFDBA
- Assistant
我们可以根据先序遍历和后序遍历的特点来重构二叉树。
首先,先序遍历的第一个节点一定是根节点,即C。我们可以在后序遍历中找到根节点C,并根据C将后序遍历分成两部分:左子树的后序遍历和右子树的后序遍历。左子树的后序遍历为GEFDB,右子树的后序遍历为BA。
接下来,我们需要确定左子树和右子树的先序遍历。可以发现,在先序遍历中,C后面的两个节点BE一定是左子树的先序遍历,后面的三个节点GDF一定是右子树的先序遍历。
现在,我们已经确定了根节点C和其左右子树的先序遍历和后序遍历,可以开始递归构建二叉树了。
代码如下:
class BinaryTreeNode: def __init__(self, val): self.val = val self.left = None self.right = None def rebuildTree(preorder, inorder): if not preorder or not inorder: return None root_val = preorder[0] root_index = inorder.index(root_val) root = BinaryTreeNode(root_val) root.left = rebuildTree(preorder[1:root_index+1], inorder[:root_index]) root.right = rebuildTree(preorder[root_index+1:], inorder[root_index+1:]) return root preorder = "CBEGDFA" inorder = "CGEFDBA" root = rebuildTree(preorder, inorder) # 测试代码 def preorderTraversal(root): if not root: return [] res = [root.val] res += preorderTraversal(root.left) res += preorderTraversal(root.right) return res def inorderTraversal(root): if not root: return [] res = inorderTraversal(root.left) res += [root.val] res += inorderTraversal(root.right) return res print("前序遍历结果为:", preorderTraversal(root)) print("中序遍历结果为:", inorderTraversal(root))输出结果为:
前序遍历结果为: ['C', 'B', 'E', 'G', 'D', 'F', 'A'] 中序遍历结果为: ['C', 'G', 'E', 'F', 'D', 'B', 'A']可以看到,先序遍历和后序遍历对应的二叉树已经重构成功。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.