算法题--求二叉树的最大深度

image.png

0. 链接

题目链接

1. 题目

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

2. 思路1: 递归实现

最大深度等于1+max(左子树的深度, 右子树的深度), 天生的递归调用了

3. 代码

# coding:utf8

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0

        if root.left is not None and root.right is not None:
            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
        if root.left is not None:
            return 1 + self.maxDepth(root.left)
        if root.right is not None:
            return 1 + self.maxDepth(root.right)
        return 1


solution = Solution()

root1 = node = TreeNode(3)
node.left = TreeNode(9)
node.right = TreeNode(20)
node.right.left = TreeNode(15)
node.right.right = TreeNode(7)

print(solution.maxDepth(root1))

输出结果

3

4. 结果

image.png