Maximum Depth of Binary Tree

第一反应是用按层次遍历，用队列做。

看了别人的代码才想起来也可以用递归去做。就是比较根的左右子树的深度，深度大的那个再加一就是根的深度了。

递归：

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int maxDepth(TreeNode *root) {
13         if(!root)
14         {
15             return 0;
16         }
17         else
18         {
19             int leftDepth,rightDepth;
20             leftDepth=maxDepth(root->left);
21             rightDepth=maxDepth(root->right);
22             return 1+(leftDepth>rightDepth?leftDepth:rightDepth);
23         }
24     }
25 };

更简洁的写法：

1 int maxDepth(TreeNode *root) {
2         if(!root)
3             return 0;
4         else
5             return 1+max(maxDepth(root->left),maxDepth(root->right));
6     }

按层次遍历用队列实现，不过这道题是计算树的深度，那就需要知道每一层什么时候遍历完的，这个怎么做呢？需要另外设置一个变量记录每一层结点的个数。

具体的就想不通了，参看http://blog.csdn.net/ithomer/article/details/8799795

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10  
11  /*
12 STL 中队列的使用(queue)
13 #include <queue>
14 
15 基本操作：
16 push(x) 将x压入队列的末端
17 pop() 弹出队列的第一个元素(队顶元素)，注意此函数并不返回任何值
18 front() 返回第一个元素(队顶元素)
19 back() 返回最后被压入的元素(队尾元素)
20 empty() 当队列为空时，返回true
21 size() 返回队列的长度
22  */
23 class Solution {
24 public:
25     int maxDepth(TreeNode *root) {
26         if(!root)
27         {
28             return 0;
29         }
30         else
31         {
32             queue<TreeNode *> Q;
33             //queue<TreeNode> Q;
34             Q.push(root);
35             TreeNode *p;
36             //int depth;//树的深度   Input:    {0} Output:    162865233 Expected:    1
37             int depth=0;
38             int count=1;//记录每一层结点的个数
39             while(!Q.empty())
40             {
41                 p=Q.front();
42                 Q.pop();
43                 count--;
44                 
45                 if(p->left)
46                 {
47                     Q.push(p->left);
48                 }
49                 if(p->right)
50                 {
51                     Q.push(p->right);
52                 }
53                 if(count==0)
54                 {
55                     depth++;
56                     count=Q.size();//下一层的结点个数
57                 }
58             }
59             return depth;
60         }
61     }
62 };

36行那里不明白，为什么我没有给depth初始化，结果就错了，C++中int类型不是默认初始化为0么。呃，好吧，刚才在codeblocks中试了一下，果然是我记错了。

《C++ primer》第四版第65页中写道：

variable initialization(变量初始化) 描述当没有给出显式初始化变量或数组元素的规则的术语。

对类类型来说，通过运行类的默认构造函数来初始化对象。如果没有默认构造函数，那么将出现编译时错误：必须要给对象指定显式的初始化式。

对于内置类型来说，初始化取决于作用域。定义在全局作用域的对象初始化为0，而定义在局部作用域的对象则未初始化，拥有未定义值。