二叉树的中序序列和后序序列来求前序序列的代码,用堆栈来实现。
时间: 2024-05-05 14:20:57 浏览: 63
以下是二叉树的中序序列和后序序列来求前序序列的代码,用堆栈来实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(inorder, postorder):
if not inorder or not postorder:
return None
root = TreeNode(postorder[-1])
stack = [root]
i, j = len(inorder)-1, len(postorder)-2
while j >= 0:
node = TreeNode(postorder[j])
parent = None
while stack and stack[-1].val == inorder[i]:
parent = stack.pop()
i -= 1
if parent:
parent.left = node
else:
stack[-1].right = node
stack.append(node)
j -= 1
return root
def preorderTraversal(root):
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
其中,`buildTree`函数用于构建二叉树,`preorderTraversal`函数用于求出前序序列。
阅读全文