104. Maximum Depth of Binary Tree [easy] (Python)

题目链接

https://leetcode.com/problems/maximum-depth-of-binary-tree/

题目原文

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.

题目翻译

给定一个二叉树，求其最大深度。
最大深度指的是，从根节点到最远的叶子节点的最长路径的节点个数。

思路方法

思路一

深度优先搜索（DFS），递归求解。

代码

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

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

思路二

广度优先搜索（BFS），利用队列求解。

代码

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

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root == None:
            return 0

        depth = 0
        q = [root]
        while len(q) != 0:
            depth += 1
            for i in range(0, len(q)):
                if q[0].left:
                    q.append(q[0].left)
                if q[0].right:
                    q.append(q[0].right)
                del q[0]
        return depth

说明
作为这个问题的对比，类似问题：Minimum Depth of Binary Tree

PS: 新手刷LeetCode，新手写博客，写错了或者写的不清楚还请帮忙指出，谢谢！
转载请注明：http://blog.csdn.net/coder_orz/article/details/51337420