代码随想录算法训练营第十五天|110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和、222.完全二叉树的节点个数

110平衡二叉树

 1 class Solution {
 2 public:
 3     int GetHeight(TreeNode* root) {
 4         if (!root) {
 5             return 0;
 6         }                       
 7         int leftHeight = GetHeight(root->left);
 8         if (leftHeight == -1) return -1; // 如果左子树不平衡，直接返回 -1
 9 
10         int rightHeight = GetHeight(root->right);
11         if (rightHeight == -1) return -1; // 如果右子树不平衡，直接返回 -1
12 
13         if (abs(leftHeight - rightHeight) > 1) {
14             return -1;
15         }
16         return max(leftHeight, rightHeight) + 1;
17     }
18 
19     bool isBalanced(TreeNode* root) {
20         return GetHeight(root) != -1;
21     }
22 };

257二叉树的所有路径

 1 class Solution {
 2 public:
 3     void preorder(TreeNode *root, vector<string> &res, string temp) {
 4         if (root == nullptr) {
 5             return;
 6         }
 7         if (!temp.empty()) {
 8             temp += "->";
 9         }
10         temp += to_string(root->val);
11         if (root->left == NULL && root->right == NULL) {
12             res.push_back(temp);
13             return;
14         }
15 
16         preorder(root->left, res, temp);
17         preorder(root->right, res, temp);
18         //push_back 是 std::vector 的方法
19     }
20     vector<string> binaryTreePaths(TreeNode* root) {
21         vector<string> res;
22         string temp = "";
23 
24         if (!root) {
25             return res;
26         }
27         preorder(root, res, temp);
28         return res;
29     }
30 };

404左叶子之和

 1 class Solution {
 2 public:
 3     void preorder(TreeNode *root, int &sum, bool isLeft) {
 4         if (root == nullptr) {
 5             return;
 6         }
 7         // 巧妙地思路 加一个bool型来判断是不是左子节点 
 8         // 如果当前节点是叶子节点，并且是左子节点
 9         if (root->left == nullptr && root->right == nullptr && isLeft) {
10             sum += root->val;
11         }
12         
13         preorder(root->left, sum, true);  // 遍历左子树，标记为左子节点
14         preorder(root->right, sum, false);  // 遍历右子树，标记为非左子节点
15     }
16 
17     int sumOfLeftLeaves(TreeNode* root) {
18         int sum = 0;
19         preorder(root, sum, false);  // 根节点不是左子节点，所以初始标记为 false
20         return sum;
21     }
22 };

222完全二叉树的节点个数

 1 class Solution {
 2 private:
 3     int getNodesNum(TreeNode* cur) {
 4         if (cur == NULL) return 0;
 5         int leftNum = getNodesNum(cur->left);      // 左
 6         int rightNum = getNodesNum(cur->right);    // 右
 7         int treeNum = leftNum + rightNum + 1;      // 中
 8         return treeNum;
 9     }
10 public:
11     int countNodes(TreeNode* root) {
12         return getNodesNum(root);
13     }
14 };