资讯专栏INFORMATION COLUMN

通过几道题目学习二叉搜索树

Steven / 717人阅读

摘要:根据这个特征,用二分法来将有序数组转换为一颗二叉搜索树。边界条件向下取整得到中间值递归二分法接下来我们验证下一棵树是否满足二叉搜索树。二验证二叉搜索树相关题目验证二叉搜索树中等思路就是,中序遍历如果满足递增的就行。

二叉树大家都知道,二叉搜索树满足以下特征:

节点的左子树只包含小于当前节点的数

节点的右子树只包含大于当前节点的数

所有左子树和右子树自身必须也是二叉搜索树

二叉搜索树也叫二叉排序树,中序遍历二叉搜索树的结果就是一次递增的遍历。 一、二叉搜索树的建立

相关题目:leetcode 108.将有序数组转换为二叉搜索树 [中等]

那么如何将一个有序数组转换为一颗二叉搜索树?

二叉搜索树的每一个分支的根节点都是他的中间值。根据这个特征,用二分法来将有序数组转换为一颗二叉搜索树。

const sortedArrayToBST = nums => {
    // 边界条件
    if (nums.length === 0) {
        return null;
    } 
    if (nums.length === 1) {
        return new TreeNode(nums[0]);
    }
    // 向下取整得到中间值
    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;
};

接下来我们验证下一棵树是否满足二叉搜索树。

二、验证二叉搜索树

相关题目:leetcode 98.验证二叉搜索树 [中等]

思路就是,中序遍历如果满足递增的就行。

用一个max作为验证值的变量,用中序遍历前面的值和后面的值作比较,一直递增则满足二叉搜索树。

const isValidBST = root => {
    let isValidBSTFlag = true;
    let max = -Number.MAX_VALUE;
    const orderSearch = root => {
        if (root) {
            orderSearch(root.left);
            if (root.val > max) {
                max = root.val;
            } else {
                isValidBSTFlag = false;
            }
            orderSearch(root.right);
        }
    }
    orderSearch(root);
    return isValidBSTFlag;
};

上一个非递归解法。

非递归中序遍历的思路就是使用栈,将节点的左子树压入直到叶节点,然后操作完左子树跟根节点后再操作右子树。

循环反复,直到栈空。

const isValidBST = root => {
    if(!root) return true;
    let stack = [];
    let isValidBSTFlag = true;
    let max = -Number.MAX_VALUE;
    while (1) {
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        if (stack.length === 0) break;
        let node = stack.pop();
        if (node.val > max) {
            max = node.val;
        } else {
            isValidBSTFlag = false;
            break;
        }
        root = node.right;
    }
    return isValidBSTFlag;
}
三、二叉搜索树的插入

相关题目:leetcode 701.二叉搜索树中的插入操作 [中等]

将值插入二叉搜索树,只要树在插入后仍保持为二叉搜索树即可。

思路:找到大于插入节点值的节点,将要插入的节点作为该节点的左子树。注意细节。

这里还是用中序遍历,中序遍历能很好地解决一种情况,就是要插入的节点值比树中的所有节点还大。

这种情况,找到树中最大值的节点,将插入的节点作为该节点的右节点。

没用递归,方便理解。

const insertIntoBST = (root, val) => {
    let stack = [];
    let r = root;
    let node = null;
    while (1) {
        while(root != null) {
            stack.push(root);
            root = root.left;
        }
        if (stack.length === 0) break;
        node = stack.pop();
        // 找到大于插入节点值的节点
        if (node.val > val) {
            let newNode = new TreeNode(val);
            newNode.left = node.left;
            // 这里是细节
            node.left = newNode;
            break;
        }
        root = node.right;
    }
    // 要插入的节点值比树中的所有节点还大
    if (val > node.val) {
        node.right = new TreeNode(val);
    }
    return r;
};
四、二叉搜索树的恢复

相关题目:leetcode 99.恢复二叉搜索树 [困难]

要求:二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下,恢复这棵树。

思路:利用中序遍历找到错误的两个节点s1,s2。交换这两个节点。

用一个数组保存遍历的值,如果前一个节点大于后一个节点,则s1肯定是前一个节点,后一个节点不一定是s2,继续遍历寻找找到s2。

const recoverTree = root => {
    let res = [];
    let s1 = s2 = null;
    const orderSearch = root => {
        if (root) {
            orderSearch(root.left);
            if (res.length !== 0) {
                if (res[res.length - 1].val > root.val) {
                    // 第一个找到的才是s1
                    !s1 && (s1 = res[res.length - 1]);
                    // 若有第二次,第二次的才是s2
                    s2 = root;
                }
            }
            
            res.push(root)
            orderSearch(root.right);
        }
    }
    orderSearch(root);
    [s1.val, s2.val] = [s2.val, s1.val];
    return root;
};
总结:

二叉搜索树跟排序相关,总是围绕着中序遍历进行操作。

递归代码简洁但是不好理解,非递归相对容易理解一些,两者效率差不太大,看场景使用。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/99424.html

相关文章

  • 几道Java集合框架面试题在面试中几乎必问

    摘要:若遇到哈希冲突,则将冲突的值加到链表中即可。之后相比于之前的版本,之后在解决哈希冲突时有了较大的变化,当链表长度大于阈值默认为时,将链表转化为红黑树,以减少搜索时间。有序,唯一红黑树自平衡的排序二叉树。 本文是最最最常见Java面试题总结系列第三周的文章。主要内容: Arraylist 与 LinkedList 异同 ArrayList 与 Vector 区别 HashMap的底层...

    bigdevil_s 评论0 收藏0
  • ⭐算法入门⭐《二叉 - 二叉搜索》简单05 —— LeetCode 897. 递增顺序搜索

    文章目录 一、题目1、题目描述2、基础框架3、原题链接 二、解题报告1、思路分析2、时间复杂度3、代码详解 三、本题小知识四、加群须知 一、题目 1、题目描述   给你一棵二叉搜索树,请按 中序遍历 将其重新排列为一棵递增顺序搜索树,使树中最左边的节点成为树的根节点,并且每个节点没有左子节点,只有一个右子节点。  样例输入: [5,3,6,2,4,null,8,1,null,null,nu...

    Soarkey 评论0 收藏0
  • 学习JavaScript数据结构与算法(四):二叉搜索

    摘要:像刚才的这幅图,就是二叉搜索树。而我们本文要学习的内容,就是如何写一个二叉搜索树。但在二叉搜索树中,我们把节点成为键,这是术语。前端路漫漫,且行且歌的前端乐园原文链接寒假前端学习学习数据结构与算法四二叉搜索树 本系列的第一篇文章: 学习JavaScript数据结构与算法(一),栈与队列第二篇文章:学习JavaScript数据结构与算法(二):链表第三篇文章:学习JavaScript数据...

    ingood 评论0 收藏0
  • PHPer面试必看:分门别类带你撸《剑指Offer》之二叉

    摘要:例如输入前序遍历序列和中序遍历序列,则重建二叉树并返回。操作给定的二叉树,将其变换为源二叉树的镜像。剑指中还有一道类似的变种题目,就是下面的这道,之字形遍历二叉树。最后下面的两道题目分别运用了二叉树先序中序遍历算法。 开篇 以下内容可能偏应试但很好理解,所以大家一定要坚持看下去,因为我们变强的过程注定孤独的,坚持下来就会看到明天的太阳。 回顾 showImg(https://user-...

    li21 评论0 收藏0

发表评论

0条评论

Steven

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<