常德网站制作公司,产品开发流程表,全屏网站 功能,重庆手机模板建站C第二阶段——数据结构和算法#xff0c;之前学过一点点数据结构#xff0c;当时是基于Python来学习的#xff0c;现在基于C查漏补缺#xff0c;尤其是树的部分。这一部分计划一个月#xff0c;主要利用代码随想录来学习#xff0c;刷题使用力扣网站#xff0c;不定时更… C第二阶段——数据结构和算法之前学过一点点数据结构当时是基于Python来学习的现在基于C查漏补缺尤其是树的部分。这一部分计划一个月主要利用代码随想录来学习刷题使用力扣网站不定时更新欢迎关注 文章目录 一、对称二叉树力扣101二、二叉树的最大深度力扣104三、二叉树的最小深度力扣111四、完全二叉树的节点个数力扣222五、平衡二叉树力扣110六、二叉树的所有路径力扣257七、左叶子之和力扣404八、找树左下角的值513九、路径总和力扣112 一、对称二叉树力扣101 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSymmetric(TreeNode* root) {if(rootNULL) return root;return isSymmetricLeftRight(root-left,root-right);}bool isSymmetricLeftRight(TreeNode* left,TreeNode* right){if(leftNULLrightNULL) return true;else if(leftNULLright!NULL) return false;else if(left!NULLrightNULL) return false;else if(left-val!right-val) return false;else{bool outside isSymmetricLeftRight(left-left,right-right);bool inside isSymmetricLeftRight(left-right,right-left);if(outside!true||inside!true){return false;}}return true;}
};二、二叉树的最大深度力扣104 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxDepth(TreeNode* root) {if(rootNULL) return 0;int leftDepth maxDepth(root-left);int rightDepth maxDepth(root-right);int result 1max(leftDepth,rightDepth);return result;}
};三、二叉树的最小深度力扣111 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int minDepth(TreeNode* root) {if(rootNULL) return 0;int leftDepth minDepth(root-left);int rightDepth minDepth(root-right);if (root-left NULL root-right ! NULL) { return 1 rightDepth;} // 当一个右子树为空左不为空这时并不是最低点if (root-left ! NULL root-right NULL) { return 1 leftDepth;}return min(leftDepth,rightDepth)1;}
};四、完全二叉树的节点个数力扣222 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int countNodes(TreeNode* root) {int count0;tr(root,count);return count;}void tr(TreeNode* root,int count){if(rootNULL) return;tr(root-left,count);tr(root-right,count);count;}
};五、平衡二叉树力扣110 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isBalanced(TreeNode* root) {if(rootNULL) return true;int result getLength(root);if(result-1) return false;return true;}int getLength(TreeNode* root){if(rootNULL) return 0;int leftLength getLength(root-left);if(leftLength-1) return -1;int rightLength getLength(root-right);if(rightLength-1) return -1;int result;if(abs(leftLength-rightLength)1) return -1;else{result max(rightLength,leftLength)1;}return result;}
};六、二叉树的所有路径力扣257 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vectorstring binaryTreePaths(TreeNode* root) {vectorstring result;vectorint path;traversal(root,path,result);return result;}void traversal(TreeNode * root,vectorint path,vectorstring result){path.push_back(root-val);if(root-leftNULLroot-rightNULL) {string temp;for(int i0;ipath.size();i){if(ipath.size()-1){temp to_string(path[i]);}else{tempto_string(path[i]);temp-;}}result.push_back(temp);return;}if(root-left){traversal(root-left,path,result);path.pop_back();}if(root-right){traversal(root-right,path,result);path.pop_back();}}
};七、左叶子之和力扣404 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {int sum0;return trv(root,sum);}// 后续遍历int trv(TreeNode *root,int sum){if(rootNULL) return 0;trv(root-left,sum);trv(root-right,sum);if(root-left!NULLroot-left-leftNULLroot-left-rightNULL){sum root-left-val;}return sum;}
};八、找树左下角的值513 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int findBottomLeftValue(TreeNode* root) {vectorvectorint result func(root);return result[result.size()-1][0];}// 层序遍历vectorvectorint func(TreeNode* root){vectorvectorint result;queueTreeNode* que;if(root!NULL) que.push(root);while(!que.empty()){vectorint vec;int Qsizeque.size();while(Qsize--){TreeNode * top que.front();que.pop();vec.push_back(top-val);if(top-left) que.push(top-left);if(top-right) que.push(top-right);}result.push_back(vec);}return result;}
};九、路径总和力扣112 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool hasPathSum(TreeNode* root, int targetSum) {vectorint sumAll;vectorint path;if(rootNULL) return false;traversal(root,path,sumAll);for(int i0;isumAll.size();i){if(sumAll[i]targetSum){return true;}}return false;}void traversal(TreeNode*root,vectorint path,vectorint result){path.push_back(root-val);if(root-leftNULLroot-rightNULL){int sum0;for(int i0;ipath.size();i){sum path[i];}result.push_back(sum);}if(root-left) {traversal(root-left,path,result);path.pop_back();}if(root-right){traversal(root-right,path,result);path.pop_back();}}};
