一.题目：二叉树的最大深度
二.算法思想
（1）递归
每个结点的深度=max{左子树深度，右子树深度}+1，左（右）子树的“根结点”也是用这个公式实现，因此可以递归实现。
（2）迭代
用层次遍历，每遍历一层就深度加一，注意一开始的初始化deep初始化为0。
三.代码
（1）递归代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if(!root) return 0; return max(maxDepth(root->left),maxDepth(root->right))+1; } };
递归也可以这样写（和上面是等价的）
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if(!root) return 0; int l=maxDepth(root->left)+1; int r=maxDepth(root->right)+1; return l>r?l:r; } };
（2）迭代代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if(root==NULL) return 0; queue<TreeNode*>que; TreeNode* node; que.push(root); int deep=0; while(!que.empty()){ int num=que.size(); for(int i=0;i<num;i++){ node=que.front(); que.pop(); if(node->right) que.push(node->right); if(node->left) que.push(node->left); } ++deep; } return deep; } };
