Leetcode: Maximum Depth of Binary Tree

题目：算出二叉树的最大深度

解决方案：（1）BFS （2）DFS

(1)BFS

一层一层往下搜索，一直找到最深的点，这里由于节点的val是没有用的，所以可以用来存储当前节点的深度，然后注意指针一定要初始化，不然在leetcode里可能会出现runtime error

/*** 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;list<TreeNode*> node_list;node_list.push_back(root);root->val=1;int maxe=1;while (node_list.size() != 0){TreeNode* now_node=NULL;//指针需要初始化now_node = node_list.front();node_list.pop_front();if (now_node->left != NULL){node_list.push_back(now_node->left);now_node->left->val=now_node->val+1;if(now_node->left->val>maxe)maxe=now_node->left->val;}if (now_node->right != NULL){node_list.push_back(now_node->right);now_node->right->val=now_node->val+1;if(now_node->right->val>maxe)maxe=now_node->right->val;}}return maxe;}
};

(2) DFS

用递归的方法来写该题的程序，代码会很简洁

/*** 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 leftmax=0, rightmax=0;leftmax=maxDepth(root->left);rightmax=maxDepth(root->right);if(leftmax>rightmax) return leftmax+1;else return rightmax+1;}
};