江西省建设厅教育网站上查询,只做旧房翻新的装修公司,项目发布网,网站默认图片素材代码随想录二刷Day16
每日任务
104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数 语言#xff1a;C
104. 二叉树的最大深度
链接#xff1a;https://leetcode.cn/problems/maximum-depth-of-binary-tree/ 递归法#xff08;前序…代码随想录二刷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;queueTreeNode* 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;queueNode* 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;queueTreeNode* 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;queueTreeNode* 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;}
};
