104二叉树的最大深度

题目: 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

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

法一: 自己的代码

思路: 遍历完一层,再遍历下一层,注意写代码前一定要先画好图,考虑各种情况,否则容易出错,

# 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
        queue1 = []
        queue2 = [1]
        queue1.append((root.left, root.right))
        max = 1
        # 这里实际上是层序遍历,queue2用于存放queue1下一层的节点,遍历完一层再一层
        while len(queue2) > 0:
            queue2 = []
            while len(queue1)>0:
                p,q = queue1.pop(0)
                if q is None and p is None:
                    pass
                else:
                    if p is None:
                        pass
                    else:
                        queue2.append((p.left, p.right))
                    if q is None:
                        pass
                    else:
                        queue2.append((q.left, q.right))
            if queue2:
                queue1 = queue2
                max += 1
            else:
                return max

if __name__ == '__main__':
    duixiang = Solution()
    root = TreeNode(1)
    a = TreeNode(2)
    b = TreeNode(3)
    root.left = a
    root.right = b
    c = TreeNode(4)
    d = TreeNode(5)
    a.left = c
    a.right = d
    e = TreeNode(6)
    d.left = e
    # # 注意这样是错的,a和root.left是两个对象,要先给a赋值,再把a赋值给root.left
    # root.left = TreeNode(2)
    # print(id(root.left))
    # root.right = TreeNode(3)
    # a = TreeNode(2)
    # print(id(a))
    # a.left = TreeNode(4)
    # a.right = TreeNode(5)
    # a.right.left = TreeNode(6)
    a = duixiang.maxDepth(root)
    print(a)

法二: 官网代码

思路: 递归,注意递归终止的条件是节点为空了,说明到分支的底部了,直接返回0,

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


作者：LeetCode
链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/solution/er-cha-shu-de-zui-da-shen-du-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。