代码随想录训练营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;}
};