LeetCode題目鏈接
https://leetcode.cn/problems/balanced-binary-tree/
https://leetcode.cn/problems/binary-tree-paths/
https://leetcode.cn/problems/sum-of-left-leaves/
https://leetcode.cn/problems/count-complete-tree-nodes/

題解
110.平衡二叉樹

想到用左子樹的高度減右子樹的高度，但遞歸不知道怎么求高度。在求高度的函數里，高度depth放在條件里還是在函數體里重新定義一個變量。用層序遍歷求高度行不行？不用遞歸？
看了題解，首先明確遞歸終止條件，遇到空結點時高度為0。接著遞歸得到左右子樹的高度，并確定一個規則，就是當遇到的樹不是平衡樹時，返回-1。但對高度判斷的條件又怎么寫呢？直接判斷是否等于-1。在后面計算result值時，要把當前結點的高度也加上，左右子樹的高度的最大值。
通過空結點傳回的高度為0確定整棵樹的高度基點，然后往上返回時都能令符合平衡二叉樹結點的”根“結點高度值加1，當某個結點不滿足平衡二叉樹的要求時，它以及它上面的所有結點高度值都將為-1。-1是個標記，標記本樹中出現了不符合平衡二叉樹的子樹。

257.二叉樹的所有路徑
知道用回溯的方法寫這道題，但不知道怎么放每次的遞歸條件。答案是當前的路徑（因為要回溯）和結果數組（題目要求string）。
自己順著思路寫了一遍代碼，小case過了，最后也過了。

404.左葉子之和
想到用遞歸去做，但是每次判斷左葉子的條件不知道怎么定，還有一個思路是對每個左結點打標記，但怎么區分左葉子結點和左普通結點。
于是看題解，從左葉子結點的父結點去判斷該結點是否是左葉子結點，這個思路其實我想到了，但一開始覺得麻煩，就沒定下來。遞歸邊界要確定，返回的是左葉子結點的值。后續的遞歸分支寫法和110.平衡二叉樹很像，但要注意求了賦值了兩次同一個值，原因是左子樹的值如果求出來了，而左葉子結點如果遞歸了返回的是0，這時需要在當前判斷求左葉子結點的值，并重新賦值覆蓋前面的。
有一個錄友說，第一個是遞歸過程，第二個是真的在求葉子結點的值。

222.完全二叉樹的節點個數
這一題是我唯一會的一題，用迭代法，任何一種遍歷順序都可以，但用遞歸法。寫成了求葉子結點個數的代碼，改了一下要加上當前結點的個數。看了一下題解，跟我寫的也差不多。

代碼

//110.平衡二叉樹
#include <iostream>
using namespace std;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) {int depth = getHeight(root);if (depth == -1) return false;else return true;}int getHeight(TreeNode* root) {if (root == NULL) return 0;int leftHeight = getHeight(root->left);int rightHeight = getHeight(root->right);if (leftHeight == -1) return -1;if (rightHeight == -1) return -1;if (abs(leftHeight - rightHeight) > 1)return -1;else return 1 + max(leftHeight, rightHeight);}
};int main() {int nums1[30] = { 3,9,20,NULL,NULL,15,7 }, nums2[30] = { 1,2,2,3,3,NULL,NULL,4,4 };TreeNode* root1 = new TreeNode(3);root1->left = new TreeNode(9);root1->right = new TreeNode(20);root1->right->left = new TreeNode(15);root1->right->right = new TreeNode(7);TreeNode* root2 = new TreeNode(1);root2->left = new TreeNode(2);root2->right = new TreeNode(2);root2->left->left = new TreeNode(3);root2->left->right = new TreeNode(3);root2->left->left->left = new TreeNode(4);root2->left->left->right = new TreeNode(4);Solution s;printf("%d", s.isBalanced(root2));return 0;
}

//257.二叉樹的所有路徑
#include <iostream>
#include <vector>
#include <string>
using namespace std;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:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if (root == NULL) return result;path.push_back(root->val);travelsal(root, path, result);return result;}void travelsal(TreeNode* cur, vector<int> &path, vector<string> &result) {if (cur->left == NULL && cur->right == NULL) {string sPath;for (int i = 0;i < path.size() - 1;i++) {sPath += to_string(path[i]);sPath += "->";}sPath += to_string(path[path.size() - 1]);result.push_back(sPath);}if (cur->left) {path.push_back(cur->left->val);travelsal(cur->left, path, result);path.pop_back();}if (cur->right) {path.push_back(cur->right->val);travelsal(cur->right, path, result);path.pop_back();}}
};int main() {int nums1[30] = { 1,2,3,NULL,5 }, nums2[30] = { 1 };TreeNode* root1 = new TreeNode(1);root1->left = new TreeNode(2);root1->right = new TreeNode(3);root1->left->right = new TreeNode(5);TreeNode* root2 = new TreeNode(1);Solution s;vector<string> result = s.binaryTreePaths(root2);for (int i = 0;i < result.size();i++) {cout << result[i] << " " << endl;}return 0;
}

//404.左葉子之和
#include <iostream>
using namespace std;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) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return 0;int leftValue = sumOfLeftLeaves(root->left);if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {leftValue = root->left->val;}int rightValue = sumOfLeftLeaves(root->right);return leftValue + rightValue;}
};int main() {int nums1[30] = { 3,9,20,NULL,NULL,15,7 }, nums2[30] = { 1 };TreeNode* root1 = new TreeNode(3);root1->left = new TreeNode(9);root1->right = new TreeNode(20);root1->right->left = new TreeNode(15);root1->right->right = new TreeNode(7);TreeNode* root2 = new TreeNode(1);Solution s;printf("%d", s.sumOfLeftLeaves(root2));return 0;
}

//222.完全二叉樹的節點個數
#include <iostream>
using namespace std;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) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return 1;int leftNum = countNodes(root->left);int rightNum = countNodes(root->right);return leftNum + rightNum + 1;}
};int main() {int nums1[30] = { 1,2,3,4,5,6 }, nums2[30] = {}, nums3[30] = {1};TreeNode* root1 = new TreeNode(1);root1->left = new TreeNode(2);root1->right = new TreeNode(3);root1->left->left = new TreeNode(4);root1->left->right = new TreeNode(5);root1->right->left = new TreeNode(6);TreeNode* root2 = nullptr;TreeNode* root3 = new TreeNode(1);Solution s;printf("%d", s.countNodes(root3));return 0;
}