JLUVicent

699修剪二叉搜索树&108将有序数组转换为二叉搜索树&538把二叉搜索树转换成累加树

 
  • 2023年 03月09日
  • 0 阅读

day23

699.修建二叉搜索树

题目链接：669. 修剪二叉搜索树

解题思路：参考 视频

使用递归方法，考虑一点，如果当前节点是要删除的节点，判断其是大于目标区间上限还是小于目标区间下限，对于不同的情况有不同的处理方法

小于目标区间下限：查询该节点的右子树有没有满足条件的，直接递归即可

大于目标区间下限：查询该节点的左子树有没有满足条件的，直接递归即可

之后再进行递归

/**
 * 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:

    // 1.确定递归参数和返回值
    TreeNode* traversal( TreeNode* node, int low, int high){
        // 2.确定终止条件
        if( node == NULL ) return NULL;
        // 3.单层逻辑 当小于low时候，找该节点的右节点有没有满足条件
        if ( node->val < low ) return traversal( node->right, low, high);
        // 当大于high，找该节点的左节点有没有比val小的
        else if( node->val > high ) return traversal( node->left,low,high);

        node->left = traversal( node->left,low,high);
        node->right = traversal( node->right,low,high);
        return node;
    }

    TreeNode* trimBST(TreeNode* root, int low, int high) {
        return traversal( root,low,high );

    }
};

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

题目链接：108. 将有序数组转换为二叉搜索树

解题思路：参考 视频

选择数组中间作为根节点，保证平衡，然后递归切割即可，注意左遍历和右遍历时候的区间

/**
 * 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:

    TreeNode* traversal( vector<int>& vec,int left,int right){
        // 2.确定终止条件 选择左闭右闭区间，中间节点作为root
        if( left > right ) return NULL;
        // 取中间节点
        int mid = (left + right ) / 2;
        // 定义新的节点
        TreeNode* node = new TreeNode(vec[mid]);
        node->left = traversal( vec,left, mid-1);    //构造左节点
        node->right = traversal( vec, mid+1,right );    //构造右子树
        return node;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traversal( nums , 0, nums.size()-1);
    }
};

538.把二叉搜索树转换成累加树

题目链接：538. 把二叉搜索树转换为累加树

题目思路：参考 视频

二叉树，因为是累加，因此从最右边开始遍历，递归法就是使用中序反过来，也就是右中左。

/**
 * 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 pre = 0;    //定义当前节点的值
    // 确定递归函数返回值和参数 返回值为空
    void traversal( TreeNode* cur){
        // 确定终止条件
        if( cur == NULL ) return;
        
        // 右
        traversal( cur->right );
        cur->val += pre ;   //中
        pre = cur->val  ;
        // 左
        traversal( cur->left );

    }

    TreeNode* convertBST(TreeNode* root) {
        traversal(root);
        return root;
    }
};
搜索