算法训练day23 LeetCode669.108.538.

669.修剪二叉搜索树

题目

669. 修剪二叉搜索树 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

• 递归

  • 不能单纯地由根节点的值直接删除单值，需要继续判断子节点是否符合条件

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

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

题目

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

题解

代码随想录 (programmercarl.com)

• 递归

  • 从数组中取中点，不断切割数组递归地构造树符合平衡二叉树的定义

  • 
    class Solution
    {
    private:
        TreeNode *traversal(vector<int> &nums, int left, int right)
        {
            if (left > right)
                return NULL;
            int mid = left + ((right - left) / 2);
            TreeNode *root = new TreeNode(nums[mid]);
            root->left = traversal(nums, left, mid - 1);
            root->right = traversal(nums, mid + 1, right);
            return root;
        }
    
    public:
        TreeNode *sortedArrayToBST(vector<int> &nums)
        {
            TreeNode *root = traversal(nums, 0, nums.size() - 1);
            return root;
        }
    };
    

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

题目

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

题解

代码随想录 (programmercarl.com)

• 递归

  • 因为二叉搜索树是有序的，每个节点的新值等于右侧子树的旧值总和--->以右左中遍历做累加

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

总结

• 树的遍历方式
  • 深度优先（栈实现）
    • 前序遍历、中序遍历、后序遍历
  • 广度优先（队列实现）
    • 层序遍历
• 树和数组转换
  • 按特定方式切割数组 --->树
  • 树按特定方式遍历 ---> 数组
• 二叉搜索数
  • 要用树和数组的视角来看待搜索树，根据其有序的特性解决问题
• 待补充