前言
今日文案：
人生总会有不期而遇的温暖和生生不息的希望，前提是你必须足够去努力，才不会错过美丽的风景和动人的故事，早安~
一、二叉树最大深度
题目来源：
解题思路1（层序）：
我们只要广度搜索，一层一层遍历，然后一层一层计数，然后最后我们就可以找出最大深度。
class Solution { public: int maxDepth(TreeNode* root) { int deep=0; queue<TreeNode*> que; //队列 if(root) que.push(root); while(!que.empty()) { int size=que.size(); //每层 for(int i=0;i<size;i++) { TreeNode*p=que.front(); que.pop(); if(p->left) que.push(p->left); if(p->right) que.push(p->right); } deep++; //每层加1 } return deep; } };
解题思路2（递归）：
解题思路：
左边遍历，右边遍历，记录返回值。
class Solution { public: int getdepth(TreeNode*root) { if(root==0) return 0; int leftdepth=getdepth(root->left); //记录左边深度 int rightdepth=getdepth(root->right); //记录右边深度 int res=max(leftdepth,rightdepth); //返回最大深度 return res+1; //加1 返回上一层 } int maxDepth(TreeNode* root) { return getdepth(root); } };
二、二叉树的最小深度
题目链接：
class Solution { public: int minDepth(TreeNode *root) { if (root == nullptr) { return 0; } if (root->left == nullptr && root->right == nullptr) { //判断左右 return 1; //叶子节点深度+1返回上一层 } int min_depth = INT_MAX; if (root->left != nullptr) { min_depth = min(minDepth(root->left), min_depth); } if (root->right != nullptr) { min_depth = min(minDepth(root->right), min_depth); } return min_depth + 1; } }
三、n叉树的最大深度
题目来源：
具体思路上一篇文章有哇。
class Solution { public: int maxDepth(Node* root) { if(root==0) return 0; int res=0; for(auto &x:root->children) //把节点遍历进去 { int D=maxDepth(x); res=max(D,res); } return res+1; } };
四、完全二叉树的节点个数
题目来源：
1、解题思路（层序）
一层一层往下刷，记录数值就可以，因为已经给定了一颗完全二叉树。
class Solution { public: int countNodes(TreeNode* root) { queue<TreeNode*> que; if (root != NULL) que.push(root); int result = 0; while (!que.empty()) { int size = que.size(); for (int i = 0; i < size; i++) { TreeNode* node = que.front(); que.pop(); result++; // 记录节点数量 if (node->left) que.push(node->left); if (node->right) que.push(node->right); } } return result; } };
2、解题思路（递归）
先求它的左子树的节点数量，再求的右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
class Solution { public: int count=0; int getcount(TreeNode*root) { if(root==NULL) { return 0; } int leftNode=getcount(root->left); //清点左右节点数量 int rightNode=getcount(root->right); return count=leftNode+rightNode+1; //+1把节点数量返回上一层 } int countNodes(TreeNode* root) { if(root==0) return 0; return getcount(root); } };
总结
冲冲冲！！！
