Leetcode之二叉树最大深度

题目:给定一个二叉树，找出其最大深度。
语言:python3
原题href：Leetcode点击跳转

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

示例形成的树

最大深度为3

分析：
求解深度问题实际上是树的递归遍历的问题，递归的主要思想是，如果传入的root节点是空的，那么深度为0，否则深度为1，然后再递归求解出左子树和右子树中深度比较大的，加上去就ok了，具体代码如下：

def maxDepth(root):
    return 0 if not root else 1 + max(maxDepth(root.left), maxDepth(root.right))

这是后来想通了优化的代码，感觉递归就是不能往下面深想，只要第一层逻辑是合理的。

贴上建树的完整的代码，方便大家测试：

from collections import deque

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
# 1 2 3 4 5 6        
def build_tree(data):
    root = TreeNode(data[0])
    queue = deque([root])
    index = 1
    while len(queue) > 0:
        if index > len(data) - 1:
            break
        node = queue.popleft()
        if index <= len(data) - 1:
            node_left = TreeNode(data[index])
            node.left = node_left
            queue.append(node_left)
        if index + 1 <= len(data) - 1:
            node_right = TreeNode(data[index + 1])
            node.right = node_right
            queue.append(node_right)
        index += 2
    return root

tree = build_tree([3, 9, 20, None, None, 15, 7])
print(tree)

总结：实际上还是树递归遍历的一种呈现方式，遇到新的问题需要看看能不能转化到已有的知识的部分来进行解决。