代码随想录算法训练营刷题复习10：二叉树、二叉搜索树复习2

二叉树、二叉搜索树 力扣题复习

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;}
};