读入一个二叉树,输出他的中序周游与后序周游序列并计算它的深度。
时间: 2024-05-10 22:21:23 浏览: 25
这道题可以用递归来实现。递归的过程中,先遍历左子树,再遍历根节点,最后遍历右子树,这就是中序遍历。而后序遍历则是先遍历左子树,再遍历右子树,最后遍历根节点。那么我们只需要在递归过程中记录遍历到的节点,就可以得到中序遍历和后序遍历结果了。
代码如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_postorder(root):
if not root:
return [], []
inorder = []
postorder = []
inorder += inorder_postorder(root.left)[0]
inorder.append(root.val)
inorder += inorder_postorder(root.right)[0]
postorder += inorder_postorder(root.left)[1]
postorder += inorder_postorder(root.right)[1]
postorder.append(root.val)
return inorder, postorder
def get_depth(root):
if not root:
return 0
left_depth = get_depth(root.left)
right_depth = get_depth(root.right)
return max(left_depth, right_depth) + 1
# 示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
inorder, postorder = inorder_postorder(root)
print("中序遍历:", inorder)
print("后序遍历:", postorder)
print("深度:", get_depth(root))
```
输出结果为:
```
中序遍历: [4, 2, 5, 1, 3]
后序遍历: [4, 5, 2, 3, 1]
深度: 3
```