给定一颗二叉树,要求输出二叉树的深度以及先序遍历二叉树得到的序列。本题假设二叉树的结点数不超过1000。
时间: 2023-11-14 19:09:03 浏览: 149
二叉树的遍历与求深度以及结点数
5星 · 资源好评率100%
二叉树的深度可以使用递归的方式求解,先判断当前节点是否为空,若为空则返回0,否则分别求出左右子树的深度,取其较大值并加1即为当前节点的深度。
先序遍历可以使用递归的方式实现,先输出当前节点的值,然后递归遍历左子树,最后递归遍历右子树。
以下是Python代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def getDepth(root):
if not root:
return 0
left_depth = getDepth(root.left)
right_depth = getDepth(root.right)
return max(left_depth, right_depth) + 1
def preorderTraversal(root):
if not root:
return []
res = [root.val]
res.extend(preorderTraversal(root.left))
res.extend(preorderTraversal(root.right))
return res
# 示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
depth = getDepth(root)
preorder = preorderTraversal(root)
print("二叉树的深度为:", depth)
print("先序遍历序列为:", preorder)
```
输出结果为:
```
二叉树的深度为: 3
先序遍历序列为: [1, 2, 4, 3]
```
阅读全文