欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 焦点 > 代码随想录训练营Day12 | 110.平衡二叉树 - 257二叉树的所有路径 - 404.左叶子之和 - 222.完全二叉树的节点个数

代码随想录训练营Day12 | 110.平衡二叉树 - 257二叉树的所有路径 - 404.左叶子之和 - 222.完全二叉树的节点个数

2024/10/31 20:00:28 来源:https://blog.csdn.net/Zuoriqiufeng/article/details/143355647  浏览:    关键词:代码随想录训练营Day12 | 110.平衡二叉树 - 257二叉树的所有路径 - 404.左叶子之和 - 222.完全二叉树的节点个数

110.平衡二叉树

  • 题目链接:110.平衡二叉树
  • 思路: 递归遍历,自底向上统计节点高度,同时比较左右节点高度,如果相差超过1,返回-1
  • 代码:
/*** 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 height(TreeNode* root) {if(!root)return 0;int leftH = height(root->left); if(leftH == -1) return -1;int rightH = height(root->right);if(rightH == -1 || abs(rightH - leftH) > 1) return -1;return max(leftH, rightH) + 1;}bool isBalanced(TreeNode* root) {return height(root) != -1;}
};

257二叉树的所有路径

  • 题目链接: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:void path(TreeNode* root, string p, vector<string>& ans) {if(!root)return;p += to_string(root->val);if(!root->left && !root->right) {ans.push_back(p);return;}path(root->left, p + "->", ans);path(root->right, p + "->", ans);}vector<string> binaryTreePaths(TreeNode* root) {vector<string> ans;string p;path(root, "", ans);return ans;}
};

404.左叶子之和

  • 题目链接: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:// e: 0 根,e:1 左节点,e: 2右节点int sumL(TreeNode* root, int e) {if(!root)return 0;if(!root->left && !root->right && e == 1)return root->val;return sumL(root->left, 1) + sumL(root->right, 2);}int sumOfLeftLeaves(TreeNode* root) {return sumL(root, 0);}
};

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

  • 题目链接:222.完全二叉树的节点个数
  • 思路:
    1. 直接编列二叉树统计节点数
    2. 根据完全二叉树特性,,左右子树中最多只有一个子树不是满二叉,统计左右子树高度,高度相等,直接返回节点数,不相等时继续递归统计节点,ps:这个思路这里并没有实现
  • 代码:
/*** 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) {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;}
};

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com