Day23——修剪二叉搜索树、将有序数组转化为二叉搜索树、把二叉搜索树转化为累加树

23天了。

目录

前言

一、修剪二叉搜索树

解题思路：

二、将有序数组转化为二叉搜索树

力扣

解题思路：

三、把二叉搜索树转化为累加树

总结

---

前言

今日文案：

人生不是一支短短的蜡烛，而是一支暂时由我们拿着的火炬。我们一定要把它燃得十分光明灿烂，然后交给下一代的人们。

                                                                                                                                 --肖伯纳

---

一、修剪二叉搜索树

力扣

解题思路：

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
		if(root==0)                //空节点直接返回
        {
            return root;
        }
        if(root->val//找到的节点
        {
            root->right=trimBST(root->right,low,high);    //因为找到的点是太小了要删除。
            return root->right;                //往右寻找才能找到可以继续链接的节点
        }
        if(root->val>high)
        {
            root->left=trimBST(root->left,low,high);
            return root->left;
        }
 
        root->left=trimBST(root->left,low,high);
        root->right=trimBST(root->right,low,high);
            return root;

---

二、将有序数组转化为二叉搜索树

力扣

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

解题思路：

有序数组构建搜索树，我们关键是找到数组中的中点作为根节点，左边的数组是小的作为左子树，右边的数组是大的，作为右子树，如此递归构建。（一般是前序遍历）

class Solution {
public:
 
	TreeNode* trasversal(vector<int>nums,int left,int right)
    {
        if(left>right)                            //判断终止条件
        {
            return NULL;
        }
		int mid=(left+right)/2;                    //中点
        TreeNode*root=new TreeNode(nums[mid]);    //构建新节点
		root->left=trasversal(nums,left,mid-1);    //遍历，此处要注意传入指针的区间
        root->right=trasversal(nums,mid+1,right);
		return root;
    }
 
    TreeNode* sortedArrayToBST(vector<int>& nums) {
		TreeNode*root=trasversal(nums,0,nums.size()-1);
    	return root;
    }
};

---

三、把二叉搜索树转化为累加树

力扣

这道题的题目就很难理解了，建议看视频。

class Solution {
public:
 
    int pre=0;
    void trasversal(TreeNode*cur)
    {
        if(cur==NULL)                    //遇到空节点就返回
        {
            return ;
        }
        trasversal(cur->right);        //遍历到右边最大的节点
        cur->val=cur->val+pre;        //相加
        pre=cur->val;                    //储存上一个节点的值
        trasversal(cur->left);          
    }
    TreeNode* convertBST(TreeNode* root) {
        trasversal(root);
        return root;
    }
};

只要找到了最大的节点（右下角），然后再从大往小遍历即可。

---

总结

构建二叉树最主要是前序遍历和选对传进数组边界条件。