题目：
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.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3/ \9 20/ \15 7
return its depth = 3.
解法一：深度优先遍历DFS
每递归一次加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 == NULL)return 0;return 1 + max(maxDepth(root->left),maxDepth(root->right));}
};
解法二：广度优先BFS
代码如下：
/*** 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 == NULL)return 0;queue<TreeNode*> Q;Q.push(root);int res = 0;while(!Q.empty()){int len = Q.size();res++;for(int i = 0; i < len; i++){TreeNode* p = Q.front();Q.pop();if(p->left)Q.push(p->left);if(p->right)Q.push(p->right);}}return res;}
};
方法三：迭代DFS
使用栈分别存储节点和深度，节点和深度同时出栈，表示当前节点的深度，然后随着节点的加深，深度增加，最后求出最大深度
代码如下：
/*** 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 == NULL)return 0;stack<TreeNode*> stk;stack<int> depStk;int depth = 1;int max = 0;while(root != NULL || !stk.empty()){while(root){stk.push(root);depStk.push(depth);root = root->left;depth++;}root = stk.top();depth = depStk.top();stk.pop();depStk.pop();if(max < depth)max = depth;root = root->right;depth++; }return max;}
};