算法Day16 | 104.二叉树的最大深度，559.n叉树的最大深度， 111.二叉树的最小深度，222.完全二叉树的节点个数

104.二叉树的最大深度

题目链接： 104.二叉树的最大深度
深度和高度相反。
高度，自然是从下向上数：叶子节点是第一层，往上数，越来越多。用后序遍历来求高度。（自己排一遍后序遍历，注意中间节点的位置，最后再处理根节点）
深度，自然是从上向下数：根节点是第一层，往下数，越来越多。用前序遍历来求深度。

递归：用后序遍历求高度（本题高度相当于深度）

class Solution {
public:int recursion(TreeNode* cur) {if (!cur) return 0;int left = recursion(cur->left);//左 int right = recursion(cur->right);//右//处理成高度，子节点数值 + 1return 1 + max(left, right);//中}int maxDepth(TreeNode* root) {return recursion(root);}
};

递归：用前序遍历求深度

class Solution {
public://每个递归函数中，都有一个resultint result = 0;//递归中用到result，也可以写到函数参数中void recursion(TreeNode* cur, int depth) {result = result > depth ? result : depth;//中。取最大值if (!cur->left && !cur->right) return;if (cur->left) recursion(cur->left, depth + 1);//左if (cur->right) recursion(cur->right, depth + 1);//右}int maxDepth(TreeNode* root) {if (!root) return 0;recursion(root, 1);return result;}
};

迭代法 层序遍历。

class Solution {
public:int maxDepth(TreeNode* root) {queue<TreeNode*> que;if (root) que.push(root);int res = 0;while (!que.empty()) {int size = que.size();while (size--) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}++res;}return res;}
};

559.n叉树的最大深度

题目链接：559.n叉树的最大深度
递归 后序遍历。

class Solution {
public:int maxDepth(Node* root) {if (!root) return 0;int depth = 0;for (auto& i: root->children) {depth = max(depth, maxDepth(i));//子节点中最高}return depth + 1;}
};

层序迭代

class Solution {
public:int maxDepth(Node* root) {queue<Node*> que;if(!root) return 0;else que.push(root);int depth = 0;while (!que.empty()) {int size = que.size();while (size--) {Node* cur = que.front();que.pop();for (auto& i : cur->children) {que.push(i);}}++depth;}return depth;}
};

---

111.二叉树的最小深度

题目链接： 111.二叉树的最小深度
递归 后序遍历

class Solution {
public:int minDepth(TreeNode* root) {if (!root) return 0;int left = minDepth(root->left);//左int right = minDepth(root->right);//右//中if (!root->left && root->right)return 1 + right;if (root->left && !root->right)return 1 + left;return 1 + min(left, right);}
};

递归前序遍历

class Solution {
public:int res = INT_MAX;void recursion(TreeNode* cur, int depth) {if (!cur) return;//中if (!cur->left && !cur->right) {res = min(res, depth);}if (cur->left) recursion(cur->left, depth + 1);//左if (cur->right) recursion(cur->right, depth + 1);//右return;}int minDepth(TreeNode* root) {if (!root) return 0;recursion(root, 1);return res;}
};

迭代 层序遍历

class Solution {
public:int minDepth(TreeNode* root) {queue<TreeNode*> que;if (!root) return 0;if (root) que.push(root);int res = 1;//至少有一层while (!que.empty()) {int size = que.size();while (size--) {TreeNode* cur = que.front();que.pop();if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);if (!cur->left && !cur->right) return res;}++res;}return res;}
};

---

222.完全二叉树的节点个数

题目链接：222.完全二叉树的节点个数
通过完全二叉树的性质，判断子树是否为满二叉树，通过 $2^k-1$来加速计算节点个数。
递归 后序遍历

class Solution {
public:int countNodes(TreeNode* root) {if (!root) return 0;//判断是否为满二叉树TreeNode* l = root->left, * r = root->right;int leftCnt = 0, rightCnt = 0;while (l) {l = l->left;++leftCnt;}while (r) {r = r->right;++rightCnt;}if (leftCnt == rightCnt) return (2 << leftCnt) - 1;//注意<<的优先级小于-的优先级int leftSum = countNodes(root->left);//左int rightSum = countNodes(root->right);//右return leftSum + rightSum + 1/*cur节点*/;//中}
};

迭代层序遍历

class Solution {
public:int countNodes(TreeNode* root) {queue<TreeNode*> que;if (!root) return 0;else que.push(root);int cnt = 0;while (!que.empty()) {int size = que.size();while (size--) {TreeNode* cur = que.front();que.pop();++cnt;if (cur->left) que.push(cur->left);if (cur->right) que.push(cur->right);}}return cnt;}
};