二叉樹、二叉搜索樹 力扣題復習

1. 110. 平衡二叉樹
2. 257. 二叉樹的所有路徑
3. 404. 左葉子之和
4. 513. 找樹左下角的值
5. 112.路徑之和
6. 113.路經總和ii
7. 450. 刪除二叉搜索樹中的節點
8. 701. 二叉搜索樹中的插入操作

110. 平衡二叉樹
左右子樹高度差要小于1
->遞歸調用（need新的函數），遇到空就返回0
->left計算左子樹高度 right計算右子樹高度
->遇到-1就返回-1
->最后計算高度差，大于1就返回-1
->回到isBalance,遇到-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 getHeight(TreeNode* node) {if(node == NULL)return 0;int left_h = getHeight(node->left);if(left_h == -1)return -1;int right_h = getHeight(node->right);if(right_h == -1)return -1;return abs(left_h-right_h) > 1 ? -1 : 1+max(left_h,right_h);}bool isBalanced(TreeNode* root) {return (getHeight(root)==-1)? false:true;}
};

257. 二叉樹的所有路徑

記錄頭結點到每個葉子節點的路徑，需要用到回溯
①traversal遞歸函數，參數root、res、path(回溯熟悉的兩件套+root)
②(前提：保證傳入函數的節點非空)
第一步，先把值存到path，（to_string）
第二步，終止條件：到達葉子節點，path寫入res，return
第三步，判斷左孩，不空，
path加入->，遞歸調用
回溯，path彈出 - 和>
第四步，判斷右孩，不空，同第三步處理

/*** 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 traversal(TreeNode* cur, string path, vector<string>& res) {path += to_string(cur->val);if(cur->left==NULL && cur->right==NULL) {res.push_back(path);return;}if(cur->left != NULL) {path += "->";traversal(cur->left,path,res);path.pop_back();path.pop_back();}if(cur->right != NULL) {path += "->";traversal(cur->right,path,res);path.pop_back();path.pop_back();}}vector<string> binaryTreePaths(TreeNode* root) {string path;vector<string> res;if(root==NULL)return res;traversal(root,path,res);return res;}
};

404. 左葉子之和

左葉子之和：
①判root空 返回0； 判root無左右孩子，返回0；
②遞歸調用有返回值：
left 記錄左子樹的左葉子之和
滿足條件：node左孩不空，node左孩沒有孩（為葉子節點），更新left值
right記錄右子樹中的左葉子之和
返回left+right一共的左葉子之和

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

513. 找樹左下角的值
層序遍歷，添加記錄每一層的第一個元素result（如果還有下一層直接把上一層的保存的值覆蓋掉就行）

class Solution {
public:int findBottomLeftValue(TreeNode* root) {queue<TreeNode*> que;int result = 0;if(root==NULL) return 0;que.push(root);while(!que.empty()) {int size = que.size();for(int i=0;i<size;i++) {TreeNode* node = que.front();que.pop();if(i==0)result = node->val;if(node->left) que.push(node->left);if(node->right) que.push(node->right);}}return result;}
};

112.路徑之和

路徑之和（這輪沒寫出來）

class Solution {
public:int traversal(TreeNode* node, int temp_sum) {if(!node->left && !node->right && temp_sum==0)return true;else if(!node->left && !node->right)return false;if(node->left) {temp_sum-=node->left->val;if(traversal(node->left,temp_sum))return true;temp_sum+=node->left->val;}if(node->right) {temp_sum-=node->right->val;if(traversal(node->right,temp_sum))return true;temp_sum+=node->right->val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(root==NULL)return false;return traversal(root,targetSum-root->val);}
};

113.路經總和ii
也是需要用到回溯，這個題和上一個題可以再復習下。

class Solution {
public:vector<vector<int>> res;vector<int> path;void traversal(TreeNode* root,int temp_sum) {if(!root->left && !root->right && temp_sum==0) {res.push_back(path);return;}else if(!root->left && !root->right)return;if(root->left) {temp_sum-=root->left->val;path.push_back(root->left->val);traversal(root->left,temp_sum);temp_sum+=root->left->val;path.pop_back();}if(root->right) {temp_sum-=root->right->val;path.push_back(root->right->val);traversal(root->right,temp_sum);temp_sum+=root->right->val;path.pop_back();}return;}vector<vector<int>> pathSum(TreeNode* root, int targetSum) {if(root==NULL)return res;path.push_back(root->val);traversal(root,targetSum-root->val);return res;}
};

450. 刪除二叉搜索樹中的節點

二叉搜索樹：比大小
==①無孩子節點，直接刪
②有左孩
左孩替代當前node
③有右孩
右孩替代當前node
③左右孩都存在
while找到右子樹的最左下的孩兒，繼承node的左子樹，然后將node更新為右孩。

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(root==nullptr)return root;if(root->val==key) {if(root->left==nullptr && root->right==nullptr) {delete root;return nullptr;}else if(root->right==nullptr) {auto retnode = root->left;delete root;return retnode;}else if(root->left==nullptr) {auto retnode = root->right;delete root;return retnode;}else {TreeNode* cur = root->right;//這里是找到右子樹的最左葉子節點while(cur->left!=nullptr) cur = cur->left;cur->left = root->left;TreeNode* temp = root;root = root->right;delete temp;return root;}}if(root->val < key) {root->right = deleteNode(root->right,key);}if(root->val > key) {root->left = deleteNode(root->left,key);}return root;}
};

701. 二叉搜索樹中的插入操作
插入一定是在葉子節點的位置，關鍵在于找到插入點的位置：二叉搜索樹的特性 比大小

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root==nullptr) {TreeNode* node = new TreeNode(val);return node;}if(root->val > val)root->left = insertIntoBST(root->left,val);if(root->val < val)root->right = insertIntoBST(root->right,val);return root;}
};