找项目网站,网站优惠券怎么做的,广州seo工程师,能力天空的网站建设优劣势669. 修剪二叉搜索树 卡哥讲的两个遍历的方法不太听得懂#xff0c;去题解找了一个和昨天的题类似的删除二叉树节点的方法#xff0c;感觉好不错。但是还是挺难写出来的#xff0c;需要判断的情况有点多#xff0c;再加上递归#xff0c;我有点泪目了。
class Solution {…669. 修剪二叉搜索树 卡哥讲的两个遍历的方法不太听得懂去题解找了一个和昨天的题类似的删除二叉树节点的方法感觉好不错。但是还是挺难写出来的需要判断的情况有点多再加上递归我有点泪目了。
class Solution {
public:// 感觉这个方法不错抄了TreeNode* dfs(TreeNode* cur, int low, int high){// 返回if (cur nullptr) return cur;// 遍历树cur-left dfs(cur-left, low, high);cur-right dfs(cur-right, low, high);// 删除节点if (cur-val low || cur-val high){// 叶子结点if (cur-left nullptr cur-right nullptr) return nullptr;// 仅存在左子树else if (cur-left ! nullptr cur-right nullptr) return cur-left;// 仅存在右子树else if (cur-left nullptr cur-right ! nullptr) return cur-right;// 左右子树都存在时else {// 左子树接到右子树的最左节点TreeNode* tmp cur-right;while (tmp-left) tmp tmp-left;tmp-left cur-left;// 返回右子树return cur-right;}}return cur;} TreeNode* trimBST(TreeNode* root, int low, int high) {// 头一次见两个递归的代码真的廷听看不懂的// if (root nullptr) return root;// if (root-val low){// TreeNode* right trimBST(root-right, low ,high);// return right;// }// if (root-val high){// TreeNode* left trimBST(root-left, low, high);// return left;// }// root-left trimBST(root-left, low, high);// root-right trimBST(root-right, low, high);// return root;return dfs(root, low, high);}
};108. 将有序数组转换为二叉搜索树 这题类似二分查找归并排序的方法先找到中间节点然后两边的分别递归继续找直到左大于右停止当左等于右的时候可以继续然后多递归一次最后返回唯一的节点。遍历过程中需要用当前的结点接住递归返回的左右孩子是一个好理解且很不错的题目。
class Solution {
public:TreeNode* traversal(vectorint nums, int left, int right){// 递归终止条件变为左大于右等于时可取因为本题左闭右闭if (left right) return nullptr;int mid (left right)/2;// 每一半数组选取中间节点向下取整建立新节点TreeNode* root new TreeNode(nums[mid]);// 左边接住返回的节点root-left traversal(nums, left, mid-1);// 右边接住返回的节点root-right traversal(nums, mid1, right);return root;}TreeNode* sortedArrayToBST(vectorint nums) {return traversal(nums, 0 ,nums.size()-1);}
};538. 把二叉搜索树转换为累加树
这题我还是比较自豪的卡哥说可以用之前学过的双指针法我就来自己尝试发现二叉搜索树从右向左遍历就可以用前一个节点的值加上本节点的值得出结果开心。递归边界什么的也比较常规关键就是中序遍历。
class Solution {
public:
// 双指针法。yydsTreeNode* pre nullptr;TreeNode* convertBST(TreeNode* root) {if (root nullptr) return root;// 从右向左中序遍历本节点的值就等于上一个节点的值加上本节点的值convertBST(root-right);if (pre ! nullptr){root-val pre-val;}pre root;convertBST(root-left);// 结尾返回根节点return root;}
};总结二叉树已经刷完了几乎所有题目都可以递归也有少部分题目迭代比较简单。掌握递归传递参数、终止条件、递归体内处理逻辑、递归是否需要返回值等。二叉树的题目以前一直喜欢但又惧怕写递归现在就是照葫芦画瓢写了一些题目但是边摸索边前进终究会有照亮的一天大话。
