二叉搜索树的数据结构及算法题解js版

写在前面

本文介绍二叉搜索树数据结构及部分操作的前端实现，及对应的部分 LeetCode 题解

节点类

class Node {constructor({value, left, right}) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

二叉搜索树类

class BST {constructor(value) {this.root = value ? new Node({value}) : null
    }
}

基本操作之插入

// 给一个值，作为节点插入树。用递归的方式实现
    insert(value) {
        // 若无根节点，插入值为根节点
        if (!this.root) {this.root = new Node({value})
        }

        let curNode = this.root
        let fn = (curNode) => {
            // 插入值可能比当前节点值大，也可能比当前节点值小
            if (value < curNode.value) {
                // 若没有左节点，则可以将待插入值插入到当前节点的左节点
                if (!curNode.left) {curNode.left = new Node({value})
                    return true;
                } else {
                    curNode = curNode.left
                    return fn(curNode)
                }
            } else if (value > curNode.value) {if (!curNode.right) {curNode.right = new Node({value})
                    return true;
                } else {
                    curNode = curNode.right
                    return fn(curNode)
                }
            } else {
                // 二叉搜索树不允许重复值。return false;
            }
        }
        return fn(curNode)
    }

基本操作之查找

// 查找某个值是否存在，返回 bool。search(value) {if (!this.root) return false;
        if (this.root.value === value) {return true;}
        let curNode = this.root;
        let fn = (curNode) => {if (value === curNode.value) return true;
            if (value < curNode.value) {
                // 搜索到尽头，没搜到，返回 false
                if (!curNode.left) {return false;} else {
                    curNode = curNode.left
                    return fn(curNode)
                }
            } else if (value > curNode.value) {if (!curNode.right) {return false;} else {
                    curNode = curNode.right
                    return fn(curNode)
                }
            }
        }
        return fn(curNode)
    }

基本操作之先序遍历

// 前序遍历
    preTraversal(root){if (!root) return [];
        let arr = []
        let curNode = this.root;
        let fn = (curNode) => {
            // 递归方式，先放根节点，再遍历左子树，再遍历右子树
            arr.push(curNode.value)
            if (curNode.left){fn(curNode.left)
            }
            if (curNode.right){fn(curNode.right)
            }
        }
        fn(curNode)
        return arr;
    }

LeetCode 对应题目题解

有了这个数据结构及基本操作之后，一些 LeetCode 算法题就可以刷过了。
下面是几道相关题和题解。

LeetCode700-easy- 二叉搜索树中的搜索

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

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function(root, val) {if (!root) {root = new TreeNode(val)
        return root;
    }

    let curNode = root
    let fn = (curNode) => {if (val < curNode.val) {if (!curNode.left) {curNode.left = new TreeNode(val)
                return root;
            } else {
                curNode = curNode.left
                return fn(curNode)
            }
        } else if (val > curNode.val) {if (!curNode.right) {curNode.right = new TreeNode(val)
                return root;
            } else {
                curNode = curNode.right
                return fn(curNode)
            }
        }
    }
    return fn(curNode)
};

589-easy- N 叉树的先序遍历

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
/**
 * @param {Node} root
 * @return {number[]}
 */
var preorder = function(root) {if (!root) return []
    let arr = []
    let curNode = root
    let fn = (curNode) => {arr.push(curNode.val);
        if (curNode.children.length){for(let i = 0; i < curNode.children.length; i++){fn(curNode.children[i])
            }
        }
    }
    fn(curNode)
    return arr
};

938-easy- 二叉搜索树的范围和

这道题是按照先序遍历拿到节点数据，组织成数组，再查找。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} L
 * @param {number} R
 * @return {number}
 */
var rangeSumBST = function(root, L, R) {if (!root) return 0;
    let arr = []
    let curNode = root;
    let fn = (curNode) => {arr.push(curNode.val)
        if (curNode.left){fn(curNode.left)
        }
        if (curNode.right){fn(curNode.right)
        }
    }
    fn(curNode)

    let sum = 0
    for(let i = 0; i < arr.length; i++){if(arr[i] <= R && arr[i] >= L){sum += arr[i]
        }
    }
    return sum;
};

总结

后续会更新剩下的基本操作和题目。
也可以直接关注作者的前端算法库：https://github.com/cunzaizhuy…
这里有近两百道 LeetCode 算法题解，持续更新中