【代码随想录二刷】Day16-二叉树-C++

代码随想录二刷Day16

每日任务

104.二叉树的最大深度
559.n叉树的最大深度
111.二叉树的最小深度
222.完全二叉树的节点个数
语言：C++

104. 二叉树的最大深度

链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
递归法（前序遍历）

class Solution {
public:int res = 0;//depth代表当前root所在层的深度void getDepth(TreeNode* root, int depth){res = res > depth ? res : depth;if(root->left == NULL && root->right == NULL) return; //中//左if(root->left){depth++;getDepth(root->left, depth);depth--;}//右if(root->right){depth++;getDepth(root->right, depth);depth--;}}int maxDepth(TreeNode* root) {if(root == NULL) return res;getDepth(root, 1);return res;}
};

递归法（后序遍历）

class Solution {
public:int getDepth(TreeNode* root){if(root == NULL) return 0;int left = getDepth(root->left); //左int right = getDepth(root->right); //右return 1 + max(left, right); //中}int maxDepth(TreeNode* root) {return getDepth(root);}
};

迭代法（层序遍历）

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

559. n叉树的最大深度

链接：https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/
递归法

class Solution {
public:int getDepth(Node* root){if(root == NULL) return 0;int res = 1;for(int i = 0; i < root->children.size(); i++){int depth = getDepth(root->children[i]) + 1;res = res > depth ? res : depth;}return res;}int maxDepth(Node* root) {return getDepth(root);}
};

迭代法（层序遍历）

class Solution {
public:int maxDepth(Node* root) {int res = 0;if(root == NULL) return res;queue<Node*> que;que.push(root);while(!que.empty()){int n = que.size();res++;for(int i = 0; i < n; i++){Node* cur = que.front();que.pop();for(int j = 0; j < cur->children.size(); j++){que.push(cur->children[j]);}}}return res;}
};

111. 二叉树的最小深度

链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
递归法（前序遍历）

class Solution {
public:int res = INT_MAX;//depth代表root所在层的深度void getDepth(TreeNode* root, int depth){if(root == NULL) return;if(root->left == NULL && root->right == NULL){res = min(depth, res);return;}//中没有处理逻辑//左if(root->left){depth++;getDepth(root->left, depth);depth--;}//右if(root->right){depth++;getDepth(root->right, depth);depth--;}}int minDepth(TreeNode* root) {if(root == NULL) return 0;getDepth(root, 1);return res;}
};

递归法（后序遍历）

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

迭代法（层序遍历）

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

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

链接：https://leetcode.cn/problems/count-complete-tree-nodes/
普通二叉树（递归-后序遍历）

class Solution {
public:int getNumber(TreeNode* root){if(root == NULL) return 0;if(root->left == NULL && root->right == NULL) return 1;int left = getNumber(root->left);int right = getNumber(root->right);return left + right + 1;}int countNodes(TreeNode* root) {if(root == NULL) return 0;return getNumber(root);}
};

普通二叉树（迭代-层序遍历）

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

完全二叉树
① 满二叉树：2^树深度-1
② 最后一层叶子节点没满：分别递归左孩子和右孩子，一定会有某个左孩子或右孩子为满二叉树

class Solution {
public:int countNodes(TreeNode* root) {if(root == NULL) return 0;int left = 0;int right = 0;TreeNode* cur = root;while(cur->left){cur = cur->left;left++;}cur = root;while(cur->right){cur = cur->right;right++;}if(left == right){return (2 << left) - 1;}return countNodes(root->left) + countNodes(root->right) + 1;}
};