Maximum Depth of Binary Tree 求二叉树的最大深度

 1 //递归方法
 2 /**
 3  * Definition for a binary tree node.
 4  * struct TreeNode {
 5  *     int val;
 6  *     TreeNode *left;
 7  *     TreeNode *right;
 8  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 9  * };
10  */
11 class Solution {
12 public:
13     int maxDepth(TreeNode* root) {
14         
15         if(root==NULL)
16             return 0;
17         int l=maxDepth(root->left);
18         int r=maxDepth(root->right);
19         
20         return l>r?l+1:r+1;
21     }
22 };
23 
24 
25 
26 //非递归的宽度优先方法
27 /**
28  * Definition for a binary tree node.
29  * struct TreeNode {
30  *     int val;
31  *     TreeNode *left;
32  *     TreeNode *right;
33  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
34  * };
35  */
36 class Solution {
37 public:
38     int maxDepth(TreeNode* root) {
39         
40         if(root==NULL)
41             return 0;
42         queue<TreeNode *> q;
43         q.push(root);
44         int nCount=1;
45         int nDepth=0;
46         while(!q.empty())
47         {
48             TreeNode * temp=q.front();
49             q.pop();
50             nCount--;
51             if(temp->left!=NULL)
52                 q.push(temp->left);
53             if(temp->right!=NULL)
54                 q.push(temp->right);
55                 
56             if(nCount==0)
57             {
58                 nDepth+=1;
59                 nCount=q.size();
60             }
61         }
62         return nDepth;
63     }
64 };