二叉树的深度（Python and C++解法）

题目：

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof

思路：

　　采用两种思路，一种是DFS中的后序遍历，另一种是BFS中的层序遍历。　　

　　树的深度优先搜索往往利用递归实现。根据此树的深度和其子树的深度之间的关系，此树的深度等于左子树的深度与右子树的深度中的最大值 +1。

　　树的层序遍历往往利用辅助数据结构实现，每遍历一层，则层计数

Python解法(DFS)：

 1 class TreeNode:
 2     def __init__(self, x):
 3         self.val = x
 4         self.left = None
 5         self.right = None
 6 
 7 class Solution:
 8     def maxDepth(self, root: TreeNode) -> int:
 9         if root is None:
10             return 0
11         leftDepth = self.maxDepth(root.left)  # 找左子树的最大深度
12         rightDepth = self.maxDepth(root.right)  # 找右子树的最大深度
13         return max(leftDepth, rightDepth) + 1

C++解法(BFS)：

 1 struct TreeNode {
 2     int val;
 3     TreeNode *left;
 4     TreeNode *right;
 5     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 6 };
 7  
 8 class Solution {
 9 public:
10     int maxDepth(TreeNode* root) {
11         int depth = 0;
12         if(root == NULL)  // 递归终止条件
13             return depth;
14         vector<TreeNode*> storeNode;  // 存储当前层节点
15         storeNode.push_back(root);
16         while(storeNode.size()) {
17             depth++;  // 更新深度
18             vector<TreeNode*> tempStoreNode;  // 存储下一层节点
19             for(TreeNode *node : storeNode) {
20                 if(node -> left)
21                     tempStoreNode.push_back(node -> left);
22                 if(node -> right)
23                     tempStoreNode.push_back(node -> right);
24             }
25             storeNode = tempStoreNode;  // 将下一层的节点复制给当前层
26         }
27         return depth;
28     }
29 };