给定一个二叉树，找出其最大深度。

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

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

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

3

/
9 20 /
15 7 返回它的最大深度 3 。

层序遍历

也就是广度优先

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        if not root:
            return ans
        queue = collections.deque()
        queue.append((root, 1))
        while queue:
            ans += 1
            for i in range(len(queue)):
                p, _ = queue.popleft()
                if p.left:
                    queue.append((p.left, 1))
                if p.right:
                    queue.append((p.right, 1))
        return ans

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        queue<TreeNode*> Queue;
        Queue.emplace(root);
        int ans = 0;
        while(!Queue.empty()) {
            int size = Queue.size();
            for (int i = 0; i < size; i++) {
                auto p = Queue.front(); Queue.pop();
                if (p->left) Queue.emplace(p->left);
                if (p->right) Queue.emplace(p->right);
            }
            ans++;
        }
        return ans;
    }
};

深度优先遍历

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        ans = 0
        if not root:
            return ans
        left_level = self.maxDepth(root.left)
        right_level = self.maxDepth(root.right)
        return max(left_level, right_level)+1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        return max(maxDepth(root->left)+1, maxDepth(root->right)+1);
    }
};