碎碎念:加油
参考:代码随想录
669. 修剪二叉搜索树
题目链接
669. 修剪二叉搜索树
思想
递归三部曲:
- 参数和返回值:返回值返回的是处理好的二叉搜索树。
- 终止条件:root==NULL 返回NULL;如果root的值小于low,注意不能直接返回NULL,因为root的右子树依然可能存在在范围内的值,所以这里要对右子树递归, 返回接收到的值;如果root的值大于high,要对左子树递归,返回接收到的返回值。
- 单层递归:左:向左递归;右:向右递归,记得分别用root的left/right把返回值接收到。
题解
// cpp
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root == nullptr) return nullptr;if (root->val < low) return trimBST(root->right, low, high);if (root->val > high) return trimBST(root->left, low, high);root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);return root;}
};
# python
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if root is None:return Noneif root.val < low:return self.trimBST(root.right, low, high)if root.val > high:return self.trimBST(root.left, low, high)root.left = self.trimBST(root.left, low, high)root.right = self.trimBST(root.right, low, high)return root
反思
108.将有序数组转换为二叉搜索树
题目链接
108.将有序数组转换为二叉搜索树
思想
注意构造的二叉树需要是平衡的。
当数组长度为奇数的时候,取中间的节点,然后左右递归分出来的数组即可
当数组长度为偶数的时候,取左侧节点和右侧节点都可以,只是结构略有不同。
递归三部曲:
- 参数和返回值
- 终止条件:区间非法left>right时,返回NULL
- 单层递归逻辑:取中间的节点,构造根节点,递归构造左子树,递归构造右子树。注意切分数组的时候的边界。注意返回值要用root的left或right接住。
题解
// cpp
class Solution {
private:TreeNode* traversal(vector<int>& 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, mid + 1, right);return root;}
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return traversal(nums, 0, nums.size() - 1);}
};
# python
class Solution:def traversal(self, nums, left, right):if left > right:return Nonemid = (left + right) // 2root = TreeNode(nums[mid])root.left = self.traversal(nums, left, mid - 1)root.right = self.traversal(nums, mid + 1, right)return rootdef sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:return self.traversal(nums, 0, len(nums) - 1)
反思
注意使用引用,否则在递归的过程中会一直copy内存的空间,这样会造成程序的性能很差,使用引用则在同一个内存地址中去操作。
注意确定区间的定义,本题用的左闭右闭。
538.把二叉搜索树转换为累加树
题目链接
538.把二叉搜索树转换为累加树
思想
二叉搜索树中序遍历得到递增的有序的序列,本题想要倒着处理,所以可以以右中左的顺序遍历。
双指针: 在遍历的过程中,始终有一个pre来记录当前cur的前一个节点的值,从而方便相加。
递归三部曲:
- 参数和返回值:传入要处理的树的根节点
- 终止条件:遍历到null,返回
- 单层递归逻辑:
右:向右递归
中:cur的值加上pre,修改pre的值
左:向左递归
题解
// cpp
class Solution {
private:int pre = 0;void traversal(TreeNode* cur) {if (cur == nullptr) return;traversal(cur->right);cur->val += pre;pre = cur->val;traversal(cur->left);}
public:TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};
# python
class Solution:def __init__(self):self.pre = 0def traversal(self, cur):if cur is None:returnself.traversal(cur.right)cur.val += self.preself.pre = cur.valself.traversal(cur.left)def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.traversal(root)return root
反思
注意理解遍历的顺序是右左中。