河南郑州网站关键词排名助手,电脑培训机构哪里有,怎么样做手机网站,网站建设情况说明书669. 修剪二叉搜索树
找到小数字的右子树与大数字左子树必须要重新检查一遍然后让root的左右直接指向return的左右节点#xff1b;
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root NULL) return NULL;if (root-val low…669. 修剪二叉搜索树
找到小数字的右子树与大数字左子树必须要重新检查一遍然后让root的左右直接指向return的左右节点
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root NULL) return NULL;if (root-val low) {// root-left trimBST(root-right, low, high);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;}
};
108. Convert Sorted Array to Binary Search Tree
这个题尝试把 root-left traversal(nums, left, mid - 1); 里面的left改成0但是不行因为left和right的数值在迭代的过程中会被mid动态替换
class Solution {
public:// 左闭右闭区间[left, right]TreeNode* traversal(vectorint nums, int left, int right) {if (left right) return NULL; //这句话是因为下面mid可能减一或者加一然后那mid减完之后还可能变成left或者right所下面的left和right不能改成0和nums.size() -1;int mid left (right - left)/2;TreeNode* root new TreeNode(nums[mid]);root-left traversal(nums, left, mid - 1); root-right traversal(nums, mid 1, right);return root;}TreeNode* sortedArrayToBST(vectorint nums) {TreeNode * root traversal(nums, 0, nums.size()-1);return root;}
}; 538.把二叉搜索树转换为累加树 注意要右中左来遍历二叉树 中节点的处理逻辑就是让cur的数值加上前一个节点的数值就是反中序来做累加 class Solution {
private:int pre 0; // 记录前一个节点的数值void traversal(TreeNode* cur) { // 右中左遍历if (cur NULL) return;traversal(cur-right);cur-val pre;pre cur-val;traversal(cur-left);}
public:TreeNode* convertBST(TreeNode* root) {traversal(root);return root;}
};
