目錄：

解題及思路學習

110.平衡二叉樹

https://leetcode.cn/problems/balanced-binary-tree/

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：

一個二叉樹每個節點?的左右兩個子樹的高度差的絕對值不超過 1 。

示例 1：

!https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg

輸入：root = [3,9,20,null,null,15,7]
輸出：true

思考：這題用迭代法好像不是特別好求。用遞歸試試。遞歸中用一個數，例如 - 1 來表示不滿足，這樣就可以簡化參數。

class Solution {
public:int getHeight(TreeNode* root) {if (root == NULL) return 0;int left = getHeight(root->left);if (left == -1) return -1;int right = getHeight(root->right);if (right == -1) return -1;return abs(left - right) > 1 ? -1 : max(left, right) + 1;}bool isBalanced(TreeNode* root) {return getHeight(root) == -1 ? false : true;}
};

257.?二叉樹的所有路徑

https://leetcode.cn/problems/binary-tree-paths/

給你一個二叉樹的根節點?root?，按?任意順序?，返回所有從根節點到葉子節點的路徑。

葉子節點?是指沒有子節點的節點。

示例 1：

!https://assets.leetcode.com/uploads/2021/03/12/paths-tree.jpg

輸入：root = [1,2,3,null,5]
輸出：["1->2->5","1->3"]

思考：主要是模擬最后保存結果的過程。

// 版本一
class Solution {
private:void traversal(TreeNode* cur, vector<int>& path, vector<string>& result) {path.push_back(cur->val); // 中，中為什么寫在這里，因為最后一個節點也要加入到path中 // 這才到了葉子節點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);return;}if (cur->left) { // 左 traversal(cur->left, path, result);path.pop_back(); // 回溯}if (cur->right) { // 右traversal(cur->right, path, result);path.pop_back(); // 回溯}}public:vector<string> binaryTreePaths(TreeNode* root) {vector<string> result;vector<int> path;if (root == NULL) return result;traversal(root, path, result);return result;}
};

c++寫代碼中，如果最后的處理節點在空節點處，則遍歷的時候不用加 if(cur→left) 這樣的判斷條件。如果處理的節點是在葉子節點，則空節點不進入處理的邏輯，需要加判斷條件。

404.左葉子之和

https://leetcode.cn/problems/sum-of-left-leaves/

給定二叉樹的根節點?root?，返回所有左葉子之和。

示例 1：

!https://assets.leetcode.com/uploads/2021/04/08/leftsum-tree.jpg

輸入: root = [3,9,20,null,null,15,7]
輸出: 24
解釋: 在這個二叉樹中，有兩個左葉子，分別是 9 和 15，所以返回 24

思考：處理邏輯是當遇到左葉子節點的時候，返回左葉子節點的值。但是判斷左葉子節點還需要父節點。

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if (root == NULL) return 0;if (root->left == NULL && root->right == NULL) return 0;int left = sumOfLeftLeaves(root->left);if (root->left && root->left->left == NULL && root->left->right == NULL) {left = root->left->val;}int right = sumOfLeftLeaves(root->right);return left + right;}
};

迭代法：

這里用了棧作為容器。使用前序遍歷。

class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {stack<TreeNode*> st;if (root == NULL) return 0;st.push(root);int result = 0;while(!st.empty()) {TreeNode* node = st.top();st.pop();if (node->left && !node->left->left && !node->left->right) {result += node->left->val;}if (node->right) st.push(node->right);if (node->left) st.push(node->left);}return result;}
};

復盤總結

個人反思

1、c++寫代碼中，如果最后的處理節點在空節點處，則遍歷的時候不用加 if(cur→left) 這樣的判斷條件。如果處理的節點是在葉子節點，則空節點不進入處理的邏輯，需要加判斷條件。

2、使用to_string函數可以將數字轉換為字符串, 返回值為轉換完的字符串。默認情況下，to_string默認輸出6位小數，但這不一定是您想要的。C ++ 11引入了std :: to_string的另一個重載版本，該版本接受一個小數位數參數。

頭文件：include<cstring>

std::to_string
string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);