跳转至

Day19 | Part9

约 98 个字 31 行代码 预计阅读时间 1 分钟

669.修剪二叉搜索树

递归: (关于多余节点如何移除 → 参考) 

1
2
3
4
5
6
7
8
TreeNode* trimBST(TreeNode* root, int low, int high) {
    if(!root) 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;
}

108.将有序数组转换为二叉搜索树

找分割点,因为有序即是中间的, 然后递归左右区间即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
TreeNode* build(vector<int>& nums, int l, int r) {
    if(l > r) return nullptr;
    int mid = l + r >> 1;
    auto node = new TreeNode(nums[mid]);
    node->left = build(nums, l, mid - 1);
    node->right = build(nums, mid + 1, r);
    return node; 
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
    return build(nums, 0, nums.size() - 1);
}

538.将二叉搜索树转为累加树

累加的顺序是右中左，只需要反中序遍历这个二叉树，然后顺序累加即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void addValue(TreeNode* root, int& sum) {
    if(!root) return;
    addValue(root->right, sum);
    sum += root->val; // 累加获得新的值
    root->val = sum; // 再赋值给root
    addValue(root->left, sum);
}
TreeNode* convertBST(TreeNode* root) {
    int sum = 0;
    addValue(root, sum);
    return root;
}

颜色主题调整

快来和我聊天~

可以的话请给我赞和 star喔~    =>  GitHub stars

评论