代码随想录算法训练营第23天 | 669.修剪二叉搜索树, 108.将有序数组转换为二叉搜索树, 538.把二叉搜索树转换为累加树, 二叉树总结

669.修剪二叉搜索树

代码随想录链接

题目

LeetCode-669.修剪二叉搜索树

给定一个二叉搜索树和一个左闭右闭的区间, 要求将二叉搜索树中不符合的节点去除, 并保持在树中节点的相对位置.

自己的想法

刚开始是想着和昨天的题目一样, 遇见一个不符合的节点就把这个节点删掉, 试着写了一分代码, 全是Run Time Error.

在看卡尔哥的写法时, 发现自己做题目还是忽略了好些二叉搜索树的性质, 没有真正去理解(也可能是上午刷题太困了)

个人感觉这道题目非常重要的一点是:

如果遇到一个节点的值在给定区间左侧(i.e. 值小于整个区间), 那么其左子树必定是要被删除的; 同理, 如果一个节点的值在给定区间的右侧(i.e. 值大于整个区间), 那么其右子树是必定会被删除的, 可以直接忽略.

题解

递归法:

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;
    }
};

迭代法:

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root) return root;
        while (root && (root -> val > high || root -> val < low)) { // 如果根节点不在目标范围内, 就移动根节点, 同时相应地抛弃一侧的子树(因为该侧子树和根节点一样, 都在给定范围之外)
            if (root -> val > high) root = root -> left;
            else root = root -> right;
        }
        TreeNode *cur = root;   // 访问子树节点的指针
        while (cur) {           // 从根节点, 沿着左指针找下去
            while (cur -> left && cur -> left -> val < low) {   // 找到一个不符合条件的节点, 使用其右子树来代替该节点和其左子树, 直至该位置的节点在范围内
                cur -> left = cur -> left -> right;
            }
            cur = cur -> left;
        }
        cur = root;             // 从根节点再次向右找不符合的节点
        while (cur) {
            while (cur -> right && cur -> right -> val > high) {    // 找到一个不符合条件的节点, 使用其左子树来代替该节点和其右子树, 直至该位置的节点在范围内
                cur -> right = cur -> right -> left;
            }
            cur = cur -> right;
        }
        return root;
    }
};

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

代码随想录链接

题目

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

将一个给定的有序数组转化为一棵平衡二叉树.

自己的想法

像从中序和后序遍历结果构建二叉树那样, 去区间中值, 左右两侧分别递归就可以.

题解

递归法:

class Solution {
private:
    TreeNode* traversal(vector<int> &nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;    // 取中间值
        TreeNode *node = new TreeNode(nums[mid]);   // 建立中间节点
        node -> left = traversal(nums, left, mid - 1);  // 左侧递归
        node -> right = traversal(nums, mid + 1, right);    // 右侧递归
        return node;    // 返回子树
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode *root = traversal(nums, 0, nums.size() - 1);
        return root;
    }
};

迭代法:

使用三个队列, 分别记录子树的根节点, 这棵子树的左区间, 以及这棵子树的右区间.

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if (nums.size() == 0) return nullptr;
        TreeNode *root = new TreeNode(0);
        queue<TreeNode*> nodeQue;   // 子树根节点, 赋值操作在下面完成
        queue<int> leftIndexes, rightIndexes;   // 相应位置的子树的左右区间
        nodeQue.push(root); // 推入根节点
        leftIndexes.push(0);    // 推入左区间
        rightIndexes.push(nums.size() - 1); // 推入右区间
        while (!nodeQue.empty()) {
            TreeNode *cur = nodeQue.front(); nodeQue.pop(); // 取子树的根节点和其左右区间
            int left = leftIndexes.front(); leftIndexes.pop();
            int right = rightIndexes.front(); rightIndexes.pop();
            int mid = left + (right - left) / 2;        // 求区间中值索引

            cur -> val = nums[mid];                     // 给子树根节点赋值
            if (left < mid) {                           // 给左子树建立根节点并推入节点队列, 推入左子树的区间
                cur -> left = new TreeNode(0);
                nodeQue.push(cur -> left);
                leftIndexes.push(left);
                rightIndexes.push(mid - 1);
            }

            if (right > mid) {                          // 给右子树建立根节点并推入节点队列, 推入右子树的区间
                cur -> right = new TreeNode(0);
                nodeQue.push(cur -> right);
                leftIndexes.push(mid + 1);
                rightIndexes.push(right);
            }
        }
        return root;
    }
};

能不能用栈来代替队列呢? 可以的, 无非就是使用队列时, 构建节点的顺序是从上至下, 从左至右; 使用栈时的顺序是从下至上, 从右至左.

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

代码随想录链接

题目

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

将二叉搜索树中每个节点的值都修改为整棵树中大于等于自己的节点的值之和.

自己的想法

中序遍历, 想着先遍历一下, 保存一个指针的数组, 再计算一堆应该修改的数, 最后通过遍历保存的数组把值给修改了.Too yong too simple, sometimes naive

其实中序遍历反过来就可以一次遍历完成操作, 反过来的操作刚好是由大到小遍历二叉搜索树.

题解

递归法:

class Solution {
private:
    int sum = 0;
    void traversal(TreeNode *root) {
        if (!root) return;
        traversal(root -> right);       // 遍历右子树
        sum += root -> val;             // 修改和
        root -> val = sum;              // 赋值节点
        traversal(root -> left);        // 遍历右子树
    }
public:
    TreeNode* convertBST(TreeNode* root) {
        traversal(root);
        return root;
    }
};

迭代法: 同样也是中序遍历反过来.

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        if (!root) return root;
        stack<TreeNode*> st;
        int sum = 0;
        st.push(root);
        while (!st.empty()) {
            TreeNode *node = st.top();
            if (node) {
                st.pop();

                if (node -> left) st.push(node -> left);

                st.push(node);
                st.push(NULL);
                
                if (node -> right) st.push(node -> right);
            } else {
                st.pop();
                node = st.top();
                st.pop();

                sum += node -> val;     // 修改和
                node -> val = sum;      // 赋值
            }
        }
        return root;
    }
};

二叉树总结

代码随想录链接

二叉树算是代码随想录里第一个这么长的篇章吧. 总共60天的训练营, 后面37天都是回溯法动态规划贪心算法, 只能说是很刺激了.