二叉搜索树|刷题合集

230. 二叉搜索树中第K小的元素

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    let count=0;
    let res;
    const traver=(root)=>{
        if (!root) return;
        traver(root.left);
        count++;
        if(count==k) res = root.val;
        traver(root.right);

    }
    traver(root);
    return res ; 
};

剑指 Offer 54. 二叉搜索树的第k大节点

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function(root, k) {
    let num,count=0;
    const tra=(root,k)=>{
        if(!root) return null;
        tra(root.right,k);
        count++; if(count==k) num=root.val;
        tra(root.left,k);
    }
    tra(root,k);
    return num;
};

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if(nums.length==0) return null; 
    let mid=Math.floor(nums.length/2);
    let root =new TreeNode(nums[mid]);
    root.left=sortedArrayToBST(nums.slice(0,mid));
    root.right=sortedArrayToBST(nums.slice(mid+1));
    return root;
};

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */


var convertBST = function(root) {
    let sum=0;
    const traver=(root)=>{
        if (!root) return null;
        traver(root.right);
        sum+=root.val;
        root.val=sum;
        traver(root.left);
    }
    traver(root);
    return root;
};

98. 验证二叉搜索树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    const judgeTree=(root,min,max)=>{
        if(!root) return true;
        if(min && root.val <= min.val) return false;
        if(max && root.val >= max.val) return false;
        return judgeTree(root.left,min,root)&&judgeTree(root.right,root,max);
    }
    return judgeTree(root,null,null);
};

700. 二叉搜索树中的搜索

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    let find=null;
    const BST=(root,val)=>{
        if(!root) return null;
        if(root.val===val) find = root;
        if(root.val<val) BST(root.right,val);
        else if(root.val>val) BST(root.left,val);
    }
    BST(root,val);
    return find;


};

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function(root, val) {
    if(!root) return new TreeNode(val);
    let find=null;
    const BST=(root,val)=>{
        if(!root) return new TreeNode(val);
        if(root.val<val) root.right= BST(root.right,val);
        else if(root.val>val) root.left= BST(root.left,val);
        return root;
    }
    BST(root,val);
    return root;    
};

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, val) {
    if(!root) return null;
    const BST=(root,val)=>{//找到相等结点
        if(!root) return null;//终止条件 
        if(root.val==val){
            if(!root.left && !root.right) return null;//判断3种情况

            else if(!root.left) return root.right;
            else if(!root.right) return root.left;
            else {//改变val，在末尾删除最小结点
                let node = findmin(root.right);//找到右子树的最小结点
                root.val=node.val;
                root.right=BST(root.right,node.val);
            }
        } 
        else if(root.val<val) root.right= BST(root.right,val);
        else if(root.val>val) root.left= BST(root.left,val);
        return root;
    }

    const findmin=(root)=>{
        while(root.left){
            root=root.left;
        }
        return root;
    }
    return BST(root,val);
};