669. 修剪二叉搜索树

二刷再看迭代法。 修剪二叉搜索树可以不用像删除二叉搜索树中的节点一样分五种情况是因为隐含的删区间有一边的树肯定不符合就不用考虑了不像删节点还要保留，所以可以简化，还是利用递归返回点跳过被删除点实现删除。

当前节点的值比区间左边界小，那左子树不用考虑，递归继续修剪右子树，并将右子树修剪后的头结点返回，跳过这一层；如果这一层在边界内，就把左/右子树的修剪结果连接到这一层根节点，完成构建；当前节点的值比区间右边界大，那右子树不用考虑，递归继续修剪左子树，并将左子树修剪后的头结点返回，跳过这一层。

//C++
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return root;
        if (root->val > high) return trimBST(root->left, low, high);
        if (root->val < low) return trimBST(root->right, low, high);
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

迭代法, 和递归的区别在于递归是从底向上重建的，而迭代是自上向下修改，所以指针要提前走一步，对于这道题，迭代法一次剪完所有左子树，而递归是左右同时剪，最好画图理解一下。因为二叉搜索树的有序性，不需要使用栈模拟递归的过程。在剪枝的时候，可以分为三步：

• 将root移动到[L, R] 范围内，注意是左闭右闭区间
• 剪枝左子树
• 剪枝右子树

public class Solution {
    public TreeNode TrimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        //处理头结点，让root移动到[L,R]范围内
        while (root != null && (root.val < low || root.val > high)) {
            if (root.val < low) root = root.right;
            else root = root.left;
        }
        TreeNode cur = root;
        //此时root已在[L,R]范围内，处理左孩子元素小于L的情况
        while (cur != null) {
            while (cur.left != null && cur.left.val < low) {
                cur.left = cur.left.right;
            }
            cur = cur.left;
        }
        cur = root;
        while (cur != null) {
            while (cur.right != null && cur.right.val > high) {
                //直到下一层符合区间
                cur.right = cur.right.left;
            }
            //下一层符合了，但其右键点还是有可能超的
            cur = cur.right;
        }
        return root;
    }
}

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

取中间节点分割区间并构建节点，然后向下递归，注意是左闭右闭区间，至于数组长度是偶数时取中间节点左侧右侧都可以，会构建出不同的平衡二叉搜索树。

• 使用引用可以避免递归copy内存空间。二刷去做一下左闭右开区间，迭代法。

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return doit(nums, 0, nums.size() - 1);
    }
    TreeNode* doit(vector<int> &nums, int left, int right) {
        if (left > right) return nullptr;//左闭右闭
        int mid = left + (right-left) / 2;
        TreeNode* newNode = new TreeNode(nums[mid]);
        newNode->left = doit(nums, left, mid - 1);
        newNode->right = doit(nums, mid + 1, right);
        return newNode;
    }
};

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

反中序，由大到小的有序数组，累加就行。

//C#
public class Solution {
    int pre = 0;
    public TreeNode ConvertBST(TreeNode root) {
        doit(root);
        return root;
    }
    public void doit(TreeNode cur) {
        if (cur == null) return;
        doit(cur.right);
        cur.val += pre;
        pre = cur.val;
        doit(cur.left);
    }
}

总结篇

二叉树的遍历方式还需要多练，多画图理解，像二叉搜索树中序遍历是有序数组这种性质，递归回溯的过程，有返回值递归接住节点构建二叉树，无返回值双指针构建二叉树。二刷看一下随想录的总结和周小结。