LeetCode 104. 二叉树的最大深度
2022-07-07 本文已影响0人
草莓桃子酪酪
题目
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明：叶子节点是指没有子节点的节点。
例：
给定二叉树 [3,9,20,null,null,15,7]，返回它的最大深度 3。
方法：递归
使用后序遍历，即最后遍历中间节点，那么此时求得的为根节点的高度，同时也是此二叉树的深度
- 判断节点是否为空
- 分别计算此时中间节点的左右子树的高度，选取更高的子树，计算深度。加一的原因是该值为中间节点的高度，从而最后求得根节点的高度
例：
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def maxDepth(self, root):
return self.depth(root)
def depth(self, node):
if node == None:
return 0
left_depth = self.depth(node.left)
right_depth = self.depth(node.right)
depth = 1 + max(left_depth, right_depth)
return depth
