二叉搜索树统一化解题模板

目录

步骤一，如何构造一颗二叉搜索树：

一.概念

二.构造二叉搜索树

步骤二，先处理再构造

实战一，来给兄弟爽一把：剑指 Offer II 052. 展平二叉搜索树

实战二，一直bug一直爽：剑指 Offer II 056. 二叉搜索树中两个节点之和

 继续秒杀，不要让战斗停下来!!!剑指 Offer II 056. 二叉搜索树中两个节点之和

 实战三，模板步骤三的具体运用：

实战:综合解决难题，效率100%剑指 Offer 33. 二叉搜索树的后序遍历序列

步骤一，如何构造一颗二叉搜索树：

一.概念

二叉搜索树又称二叉排序树，具有以下性质：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树

 请牢牢的记住这句话：中序遍历二叉搜索树等于遍历有序数组。

二.构造二叉搜索树

当我们遍历有序数组时候，他的中间值就是根节点。所以我们每次都取数组的中间值当根节点，同时该数组一分为二变为左数组，右数组，不断重复该过程，直到数组的大小为零即构建完成。

class Solution {
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        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;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

因为每一个过程都是相同的，所以符合递归性质。

left 和 right 用于控制每个新数组的大小，当left>right 时代表数组的大小为0递归结束。

所以终止条件是left>right.

操作过程： 创建新的节点 new TreeNode (nums[mid])。

最后一层递归条件：root 左子树结果返回给根节点。 root->left = traversal(nums, left, mid - 1);

                                root 右子树结果返回给根节点。 root->right = traversal(nums, mid+1,right);

这里着重强调一下边界条件：

因为traveral（nums,left,right） 是【  left  ，right 】 是左闭右闭。所以每次划分得抛去mid 。

不清楚递归的可以看我的这篇博客      递归统一化模板 。

步骤二，先处理再构造

接下来教大家如何卡BUG！

所有二叉搜索树的题的逻辑就是，对二叉搜索树进行增删查改。 因为中序遍历二叉搜索树等于遍历有序数组，所以我们把二叉搜索树转化为有序数组，对数组的增删查该还不爽么？？

之后我们再把数组重新构件成二叉树就行了！

所以遇见二叉搜索树不要再想什么BFS，DFS 递归，回溯之类的。 咱们直接降维打击就行。

提供一下模板：

第一步：二叉搜索树转化为有序数组

    vector<int> V;
    void travel (TreeNode* root)
    {
        if(root==nullptr) return;
        travel(root->left);
        V.push_back(root->val);
        travel(root->right);
    } 
   

第二步：对数组进行增删查改

             这一步对vector进行操作。

第三步：重新构造搜索二叉树

根据中序遍历数组构造二叉树

class Solution {
private:
    TreeNode* traversal(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        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;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

实战一，来给兄弟爽一把：剑指 Offer II 052. 展平二叉搜索树

class Solution {
public:
    vector<int> V;
    void travel (TreeNode* root)
    {
        if(root==nullptr) return;
        travel(root->left);
        V.push_back(root->val);
        travel(root->right);
    } 
     
//首先中序遍历，转化为有序数组

    TreeNode* increasingBST(TreeNode* root) {
        travel(root);

        TreeNode* pre=new TreeNode(V[0]);
        //这里先创建一下pre节点方便后面节点接上去。
        auto head=pre;
        //记录一下根节点，因为pre和cur节点都是在不断移动的，把最开始的头结点保存下来
        
        for(int i=1;i<V.size();i++)
        {
            TreeNode* cur=new TreeNode(V[i]);
            pre->right=cur;
            pre=cur;
        }
    //重新构造一颗二叉树

        return head;
    }
};

实战二，一直bug一直爽：
剑指 Offer II 056. 二叉搜索树中两个节点之和

 二话不说直接上模板：
1.先构造vector有序数组
2.对数组进行增删查改
ps：此题还没用到模板三。

class Solution {
public:
    vector<int> V;
    void travel (TreeNode* root)
    {
        if(root==nullptr) return;
        travel(root->left);
        V.push_back(root->val);
        travel(root->right);
    } 
     
    int kthLargest(TreeNode* root, int k) {
        travel(root);
        return V[V.size()-k];
    }
};

 继续秒杀，不要让战斗停下来!!!剑指 Offer II 056. 二叉搜索树中两个节点之和

 二话不说直接上模板：
1.先构造vector有序数组
2.对数组进行增删查改
ps：此题还没用到模板三。

class Solution {
public:
    vector<int> V;
    void travel (TreeNode* root)
    {
        if(root==nullptr) return;
        travel(root->left);
        V.push_back(root->val);
        travel(root->right);
    } 
     //构造有序数组vector

    bool findTarget(TreeNode* root, int k) {
        travel(root);
        for(int i=0;i<V.size();i++)
        {
            for(int j=i+1;j<V.size();j++)
            {
                if(V[i]+V[j]==k) return true;
            }
        }
        return false;
     //对数组进行操作，寻找是否存在两数之和
    }
};

 实战三，模板步骤三的具体运用：

补充步骤三的模板，我们知道了如何用中序遍历构造二叉树搜索树，却不了解根据前序，后续遍历数组如何重构二叉树。

接下来丰富我们的武器库！！

后续遍历数组构造二叉搜索树

 后续遍历数组特点：最后一个节点是root节点

 然后我们需要找到分界点mid ，将剩下的划分为左数组，和右数组，左边数组接在root->left上

右边数组接在root->right上。

TreeNode* traversal(vector<int>& nums,int left ,int right) {
    if(left>right) return nullptr;
    TreeNode* root=new TreeNode(nums[right]);
    int mid=right;
    for(int i=left;i<right;i++)
    {
        if(nums[right]<=nums[i])
        {
            mid=i;
            break;
        }
    }
    root->left=traversal(nums,left,mid-1);
    root->right=traversal(nums,mid,right-1);
    return root;
    }

这里不想细讲递归如何写此代码（默认有递归基础，没有的请看我的递归模板）。

补充：递归统一化模板

 前序遍历数组构造二叉搜索树:1008. 前序遍历构造二叉搜索树

 真的是不能小觑啊，这些模板每一个单独拉出来讲都是一道中等题！！！

但是我们的目标是统一化解决这一类题，虽然前期铺垫麻烦，但是我们能够保证100%做对，并且

100%有思路。

   TreeNode* traversal(vector<int>& nums,int left ,int right) {
       if(left>right) return nullptr;
       TreeNode* root=new TreeNode(nums[left]);
       int mid=left;
       for(int i=right;i>left;i--)
       {
           if(nums[i]<=nums[left])
           {
               mid=i;
               break;
           }
       }
       root->left=traversal(nums,left+1,mid);
       root->right=traversal(nums,mid+1,right);
       return root;
   } 

 

实战:综合解决难题，效率100%剑指 Offer 33. 二叉搜索树的后序遍历序列

class Solution {
public:
TreeNode* traversal(vector<int>& nums,int left ,int right) {
    if(left>right) return nullptr;
    TreeNode* root=new TreeNode(nums[right]);
    int mid=right;
    for(int i=left;i<right;i++)
    {
        if(nums[right]<=nums[i])
        {
            mid=mid== right?i:mid;
        }
    }
    root->left=traversal(nums,left,mid-1);
    root->right=traversal(nums,mid,right-1);
    return root;
    }
    vector<int> V;
    void travel (TreeNode* root)
    {
        if(root==nullptr) return;
        travel(root->left);
        V.push_back(root->val);
        travel(root->right);
    } 
      
    bool verifyPostorder(vector<int>& postorder) {
        if(postorder.size()==0) return true;
    TreeNode* tree=traversal(postorder,0,postorder.size()-1);
    travel(tree);
    for(int i=0;i<V.size()-1;i++)
    {
        if(V[i]>V[i+1])
        {
            return false;
        }
    }
    return true;
    }
};