669. 修剪二叉搜索树

难。没来得及弄。周六做

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

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

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

#答案自己敲的。不够简洁。有空看一下答案
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        int size = nums.size();
        if (size == 0) {
            return nullptr;
        }
        int mid = size/2;
        TreeNode* root = new TreeNode(nums[mid]);
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        
        if (mid > 0) {
            vector<int> leftNums(nums.begin(), nums.begin() + mid);
            left = sortedArrayToBST(leftNums);
        }

        if (mid < size) {
            vector<int> rightNums(nums.begin() + mid + 1, nums.end());
            right = sortedArrayToBST(rightNums);
        }
        root->left = left;
        root->right = right;
        return root;
    }
};

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

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

tree.png

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

关键点是读懂题目，先右后左

递归

public:
    void travelSal(TreeNode* root) {
        if (root != nullptr) {
            travelSal(root->right);
            root->val += pre;
            pre = root->val;
            travelSal(root->left);
        }
    }
    TreeNode* convertBST(TreeNode* root) {
        travelSal(root);
        return root;
    }
};

迭代

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int pre = 0;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        while(!st.empty() || cur != nullptr) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->right;
            } else {
                cur = st.top();
                st.pop();
                cur->val += pre;
                pre = cur->val;
                cur = cur->left;
            }
        }
        return root;
    }
};