代码随想录 | Day27 | 二叉树：将有序数组转换为二叉搜索树&&二叉搜索树转换为累加树

主要学习内容：

1.构建二叉树

2.二叉搜索树转换为累加树的思路，主要是性质的运用

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

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

解法思路：

和从中序和后序构建二叉树一个思路

1.函数参数和返回值

1
TreeNode *tra(vector<int> nums)

返回当前已经构建好的结点，如果不返回这个的话，我们无法的得到构建好的根节点，传入的是构建以当前节点为根结点的子树需要的数

2.终止条件

直到没有数即没有结点要构建就是结束

1
2
if(nums.size()==0)
	return nullptr;

3.本层代码逻辑

首先将数组正中间的值设为根结点，即数组的分割点，因为我们要构建的是二叉搜索树

左子树就是前半段，右子树就是后半段，然后递归调用前半段和后半段就行

我这里用的是左闭右开区间，左子树 [0,index)，右子树[index+1,end)

可以选择其他的区间，但是一定要统一

最后把左右子树都赋值完毕的根结点返回给上层调用函数

1
2
3
4
5
6
7
8
//设置根结点
int index=nums.size()/2;
TreeNode *t=new TreeNode(nums[index]);
//左右子树赋值
t->left=tra(vector<int>(nums.begin(),nums.begin()+index));
t->right=tra(vector<int>(nums.begin()+index+1,nums.end()));
//返回当前结点给上层递归函数
return t;

这里我们无需担心平衡与否的问题，因为平常构建二叉树也是从中间开始构建，构建出来的一般就是平衡二叉树

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode *tra(vector<int> nums)
    {
        if(nums.size()==0)
            return nullptr;
        int index=nums.size()/2;
        TreeNode *t=new TreeNode(nums[index]);
        t->left=tra(vector<int>(nums.begin(),nums.begin()+index));
        t->right=tra(vector<int>(nums.begin()+index+1,nums.end()));
        return t;

    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return tra(nums);
    }
};

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

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

思路：

代码并不难写，难的是思路

我们知道一个二叉搜索树是一个有序序列

如果让我们把一个数组变成累加数组，即当前值变成大于等于他的所有值之和

比如

[1,2,3]变成[6,5,3] 那就直接从后往前遍历，记录后面的值，然后挨个往前加，比如pre保存3，遇到2就加上pre，然后pre变成5，依次往后

本来二叉搜索树的有序数组要中序遍历左中右得到[1,2,3]，我们要得到比当前节点大的所有值的和，那现在要从后往前遍历，那当前是右中左即可，现在来看代码实现

1.函数返回值和参数

1
2
TreeNode *pre=nullptr;
void tra(TreeNode *t)

pre记录前一个结点的值（或者说它前面的所有值之和）

2.终止条件

遇到空的不加

1
2
if(t==nullptr)
	return ;

3.本层逻辑

1
2
3
4
5
tra(t->right);
if(pre!=nullptr)
	t->val+=pre->val;
pre=t;
tra(t->left);

遍历顺序右中左

如果pre不为空，即已经记录到了值，那就当前结点加上它前面的，因为它前面的一定都比它大

加完后更新pre的值（pre在更新过程中会自动成为前面所有值的和）

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    TreeNode *pre=nullptr;
    void tra(TreeNode *t)
    {
        if(t==nullptr)
            return ;
        tra(t->right);
        if(pre!=nullptr)
            t->val+=pre->val;
        pre=t;
        tra(t->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        tra(root);
        return root;
    }
};

代码随想录版本，就是把记录前一个结点换成了记录前一个结点的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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) {
        pre = 0;
        traversal(root);
        return root;
    }
};

二叉树章节结束