百度公司网站怎么做,wordpress的ssl,网站管理cms,辛集建设网站二叉树、二叉搜索树 力扣题复习
110. 平衡二叉树257. 二叉树的所有路径404. 左叶子之和513. 找树左下角的值112.路径之和113.路经总和ii450. 删除二叉搜索树中的节点701. 二叉搜索树中的插入操作
110. 平衡二叉树 左右子树高度差要小于1 -递归调用#xff08;need新的函…二叉树、二叉搜索树 力扣题复习
110. 平衡二叉树257. 二叉树的所有路径404. 左叶子之和513. 找树左下角的值112.路径之和113.路经总和ii450. 删除二叉搜索树中的节点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 : 1max(left_h,right_h);}bool isBalanced(TreeNode* root) {return (getHeight(root)-1)? false:true;}
};257. 二叉树的所有路径
记录头结点到每个叶子节点的路径需要用到回溯 ①traversal递归函数参数root、res、path(回溯熟悉的两件套root) ②(前提保证传入函数的节点非空) 第一步先把值存到pathto_string 第二步终止条件到达叶子节点path写入resreturn 第三步判断左孩不空 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, vectorstring res) {path to_string(cur-val);if(cur-leftNULL cur-rightNULL) {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();}}vectorstring binaryTreePaths(TreeNode* root) {string path;vectorstring res;if(rootNULL)return res;traversal(root,path,res);return res;}
};404. 左叶子之和
左叶子之和 ①判root空 返回0 判root无左右孩子返回0 ②递归调用有返回值 left 记录左子树的左叶子之和 满足条件node左孩不空node左孩没有孩为叶子节点更新left值 right记录右子树中的左叶子之和 返回leftright一共的左叶子之和
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {if(rootNULL)return 0;if(root-leftNULL root-rightNULL)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) {queueTreeNode* que;int result 0;if(rootNULL) return 0;que.push(root);while(!que.empty()) {int size que.size();for(int i0;isize;i) {TreeNode* node que.front();que.pop();if(i0)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_sum0)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_sumnode-left-val;}if(node-right) {temp_sum-node-right-val;if(traversal(node-right,temp_sum))return true;temp_sumnode-right-val;}return false;}bool hasPathSum(TreeNode* root, int targetSum) {if(rootNULL)return false;return traversal(root,targetSum-root-val);}
};113.路经总和ii 也是需要用到回溯这个题和上一个题可以再复习下。
class Solution {
public:vectorvectorint res;vectorint path;void traversal(TreeNode* root,int temp_sum) {if(!root-left !root-right temp_sum0) {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_sumroot-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_sumroot-right-val;path.pop_back();}return;}vectorvectorint pathSum(TreeNode* root, int targetSum) {if(rootNULL)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(rootnullptr)return root;if(root-valkey) {if(root-leftnullptr root-rightnullptr) {delete root;return nullptr;}else if(root-rightnullptr) {auto retnode root-left;delete root;return retnode;}else if(root-leftnullptr) {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(rootnullptr) {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;}
};
