[数据结构与算法]力扣周结05

本周的力扣周结我并没有刷很多的题，回溯模块最近才开始刷，先把树巩固好

700. 二叉搜索树中的搜索

解题思路

利用二叉搜索树的性质去寻找指定值的结点（假设树中结点没有重复元素），二叉搜索树中根节点的左孩子一定小于其根节点，根节点的右孩子一定大于其根节点，因为我们需要返回指定的子树所以，我们递归函数的返回值不为空

核心代码

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        //递归结束的标志是找到了符合题目要求的根节点或是遍历到了空结点
        if(root == null || root.val == val){
            return root;
        }
        TreeNode node = null;
        if(root.val > val){
            node = searchBST(root.left, val);
        }
        if(root.val < val){
            node = searchBST(root.right, val);
        }
        return node;
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

98. 验证二叉搜索树

解题思路

中序遍历二叉搜索树，要遍历每一个结点判断每一个结点都是否符合二叉搜索树的性质。

核心代码

class Solution {
    //进阶：不使用额为的空间
    TreeNode max;

    public boolean isValidBST(TreeNode root) {
        //遍历到叶子节点
        if(root == null) {
            return true;
        }

        //左
        if(!isValidBST(root.left)) {
            return false;
        }

        //中
        if(max != null && root.val <= max.val) {
            return false;
        }
        max = root;

        //右
        return isValidBST(root.right);
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

530. 二叉搜索树的最小绝对差

解题思路

这道题和上一题的思路大概一致，要中序遍历每个二叉搜索树的结点，并且要记录父结点，用于上一层的调用

核心代码

class Solution {

    TreeNode node;
    int min = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return min;
    }

    public void inorder(TreeNode root) {
        //遍历到叶子结点
        if(root == null) {
            return;
        }
        inorder(root.left);
        if(node != null && root.val - node.val < min) {
            min = root.val - node.val;
        }
        node = root;
        inorder(root.right);
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

501. 二叉搜索树中的众数

解题思路

这道题力扣虽然表为easy是因为可以使用暴力破解，如果使用纯递归的的话，还是比较难的，还是利用二叉搜索树的性质，中序遍历相当于从小到大遍历，使用一个ThreeNode类型来记录前驱结点，使用一个额外的空间来记录出现的次数，如果当前结点和前驱结点不等就重新记录

核心代码

class Solution {
    //记录出现的最大值次数
    int max = 1;
    //记录前驱元素的出现次数
    int temp = 1;
    //记录前驱元素
    TreeNode node;
    //定义结果集
    ArrayList<Integer> mode = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        inorder(root);
        int[] result = new int[mode.size()];
        for(int i = 0; i < result.length; i++) {
            result[i] = mode.get(i);
        }
        return result;
    }

    //相当于是求递增序列的众数
    public void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        //当前结点的前一个结点如果不等就直接让temp = 1
        if(node == null || root.val != node.val) {
            temp = 1;
        } else {
            temp++;
        }
        if(temp > max) {
            mode.clear();
            mode.add(root.val);
            max = temp;
        } else if (temp == max) {
            mode.add(root.val);
        }
        node = root;
        inorder(root.right);
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

236. 二叉树的最近公共祖先

解题思路

寻找最近的公共祖先，如果发现一个结点，它的左子树和右子树分别包括左右结点那么就找到了公共祖先，所以我们可以后序遍历二叉树

核心代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //递归结束的条件遍历到目标结点或是空结点
        if(root == p || root == q || root == null) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //如果左右结点不为空就证明找到了结点，返回当前结点
        if(left != null && right != null) {
            return root;
        }
        //如果左子树为空直接返回右子树即可
        //右子树有两种情况：1.为空 2.不为空
        if(left == null) {
            return right;
        }
        //左子树不为空，右子树为空
        return left;
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

235. 二叉搜索树的最近公共祖先

解题思路

区别于上一道题，这道题的搜索可以依赖于二叉树的性质，如果要寻找的结点的值都大于根结点那么就寻找他的右子树，如果寻找的结点的值都小于根节点那么就寻找左子树，如果都不是就证明寻找的值分布在跟结点的两侧，直接返回根节点即可。

核心代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //如果两个结点的值比父结点大，那么一定在右侧
        if(p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        return root;
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

701. 二叉搜索树中的插入操作

解题思路

二叉搜索树的插入是不需要破坏原有树的结构的，所以我们直接利用二叉搜索树的性质即可完成插入

核心代码

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        //如果结点为空那么就返回空结点
        if(root == null) {
            root = new TreeNode(val);
            return root;
        }
        //如果父结点的值比val大那就一定插入在左子树
        if(root.val > val) {
            root.left = insertIntoBST(root.left, val);
        } else if (root.val < val) { //如果父结点的值比val小那就一定插入在右子树
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

450. 删除二叉搜索树中的节点

解题思路

删除二叉树的结点，情况涉及的就比较多了，这五种情况必须全部考虑到

1. 如果删除的是叶子结点，那么直接删除就好了
2. 如果删除的结点右孩子不为空，那么删除结点返回右孩子就好了
3. 如果删除的结点左孩子不为空但是右孩子为空，那么直接删除结点返回左孩子就好了
4. 如果删除的结点左右孩子都不为空，那么就将左孩子的根节点连接到，右孩子最左子树的根节点上
5. 如果就找不到删除结点，直接返回根节点即可

这道题不需要遍历所有的结点，只需要删除待删除的结点返回最终结果即可

核心代码

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //1.找不到该结点遍历到叶子结点直接返回
        if(root == null) {
            return root;
        }
        //如果找到这个结点
        if(root.val == key) {
            //2.如果结点的左右孩子都为空，那么直接删除该结点即可
            if(root.left == null && root.right == null) {
                return null;
            //3.如果结点的左孩子不为空，右孩子为空那么就将右孩子移上去
            }else if (root.left != null && root.right == null) {
                root = root.left;
                return root;
            //4.如果结点的右孩子不为空，左孩子为空那么就将左孩子移上去
            }else if (root.left == null && root.right != null) {
                root = root.right;
                return root;
            //5.如果结点左右孩子都不为空，那么就将左孩子的跟结点移动到有孩子的根节点的最左根节点的左孩子，然后右孩子移动到根节点
            }else if (root.left != null && root.right != null) {
                TreeNode temp = root.right;
                while(temp.left != null) {
                    temp = temp.left;
                }
                temp.left = root.left;
                root = root.right;
                return root;
            }
        }
        if(key < root.val) {
            root.left = deleteNode(root.left, key);
        }else {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

669. 修剪二叉搜索树

解题思路

这道题和450基本类似，好多题都能看到卡哥的用心良苦，这套力扣刷题攻略我已经走了大半学到了很多东西，从刚开始的恐惧算法到现在每天不刷两三个小时浑身不自在，感谢卡哥

核心代码

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        //1.如果结点为空
        if(root == null) {
            return root;
        }
        //左
        root.left = trimBST(root.left, low, high);
        //右
        root.right = trimBST(root.right, low, high);
        //中 找到不在范围内的根节点
        if(root.val < low || root.val > high) {
            //2.根节点的左右孩子都为空直接删除该结点即可
            if(root.left == null && root.right == null) {
                root = null;
                return root;
            //3.左孩子不为空右孩子为空
            }else if (root.left != null && root.right == null) {
                root = root.left;
                return root;
            //4.右孩子不为空左孩子为空
            }else if (root.left == null && root.right != null) {
                root = root.right;
                return root;
            //5.左右孩子都不为空
            }else {
                TreeNode temp = root.right;
                while(temp.left != null) {
                    temp = temp.left;
                }
                temp.left = root.left;
                root = root.right;
                return root;
            }
        }
        return root;
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

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

解题思路

注意越界条件

核心代码

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length  - 1);
    }

    //区间的定义，左闭右闭
    public TreeNode build(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 = build(nums, left, mid - 1);
        root.right = build(nums, mid + 1, right);
        return root;
    }
}

时间复杂度

O(n)

空间复杂度

O(logn)

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

解题思路

这道题的难点应该是在于对题目的理解吧

核心代码

class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if(root == null) {
            return null;
        }
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }
}

时间复杂度

O(n)

空间复杂度

O(n)