給定一個二叉樹 root ，返回其最大深度。

二叉樹的 最大深度 是指從根節點到最遠葉子節點的最長路徑上的節點數。

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：3

示例 2：

輸入：root = [1,null,2]
輸出：2

解題思路

DFS,以示例1為例子

1.初始化調用：函數首先被調用為 maxDepth(root)，其中 root 是樹的根節點，其值為 3。
2.進入遞歸：

• 對于根節點（3），它有兩個子節點（9 和 20），因此會遞歸調用左子樹的 maxDepth(root->left) 和右子樹的 maxDepth(root->right)。

• 左子樹遞歸： 進入左子樹（9），此節點沒有子節點，所以返回 0 + 1 = 1。

• 右子樹遞歸： 進入右子樹（20），它有兩個子節點（15 和 7）。

• 對于節點 20，繼續遞歸： 左子樹（15）沒有子節點，返回 0 + 1 = 1。 右子樹（7）也沒有子節點，返回 0 + 1 = 1。

• 在節點 20處，左右子樹的最大深度為 1，所以返回 max(1, 1) + 1 = 2。

• 回到根節點（3）處，其左右子樹的最大深度分別為 1（來自9的路徑）和 2（來自20的路徑），因此返回 max(1, 2) + 1 = 3。

結果：整個函數執行完畢后，返回的是整棵樹的最大深度，即 3

/*** 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), maxDepth(root->right)) + 1;}
};