五月刷题20——二叉搜索树

• • 前言
  • 一、今日题目
  • 二、解题思路
  • • 1. 700. 二叉搜索树中的搜索
    • 2. 230. 二叉搜索树中第K小的元素
    • 3.145. 二叉树的后序遍历
    • 4. 1382. 将二叉搜索树变平衡

• 一个算法废材的刷题之路开更了, 更新每天刷题的题解内容
• 注重个人理解，看难度更新题目数量
• 题目来源于力扣
• 新开专栏，争取每日都能做出至少一题=v=
• 语言java、python、cc++

1. 700. 二叉搜索树中的搜索
2. 230. 二叉搜索树中第K小的元素
3. 108. 将有序数组转换为二叉搜索树
4. 1382. 将二叉搜索树变平衡

1. 利用二叉搜索树的特性，查找即可

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        
        if(root.val > val){
            return searchBST(root.left, val);
        }
        else if(root.val < val){
            return searchBST(root.right, val);
        }
        return root;
    }
}

1. 定义两个全局变量，一个用来记录结果，一个用来统计查找次数
2. 中序遍历查找第k个数

class Solution {
    public int ans = 0;  // 用来记录结果
    public int count = 0;  // 用来统计次数
    public void midTraverse(TreeNode root){
        if (root == null) return;
        midTraverse(root.left);  // 中序遍历
        count--;  // 经过一个节点，将count--
        // 如果此时count为0，说明当前节点就是要找的结果
        if(count == 0){  
            ans = root.val;
        }
        midTraverse(root.right);
    }
    public int kthSmallest(TreeNode root, int k) {
        count = k;  // 将次数赋值给全局变量
        midTraverse(root);
        return ans;
    }
}

理解透彻再回来补上

理解透彻再回来补上