关于二叉搜索树的一些总结

坦率地讲,我一直觉得树这个结构特别复杂,主要是我搞不太清楚递归的过程,所以老是忘(就在刚才,我又忘了怎么把一个有序数组变成BST),主要还是不理解吧……所以就总结一下,方便下次查询。

二叉搜索树BST是一个很常见的结构,并且有一些特别好的性质:

  1. 节点 N 左子树上的所有节点的值都小于等于节点 N 的值
  2. 节点 N 右子树上的所有节点的值都大于等于节点 N 的值
  3. 左子树和右子树也都是 BST

因为有这样的特点,所以BST有一个很重要的特点:中序遍历的结果事实上是一个有序的数组。可以利用这个性质解决一些问题。

此外,为方便说明,下文中的TreeNode结构体定义如下:

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

首先是把有序数组转换成BST,这个可以利用二分法来实现:

TreeNode *getBST(vector<int> &nums, int b, int e)
{
    if (b == e)
    {
        return new TreeNode(nums[b]);
    }
    if (b > e)
    {
        return nullptr;
    }
    int mid = (b + e + 1) / 2;
    TreeNode *root = new TreeNode(nums[mid]);
    root->left = getBST(nums, b, mid - 1);
    root->right = getBST(nums, mid + 1, e);
    return root;
}

如果数据量较大,中间求mid的过程可以改成类似于b + ( e - b ) / 2,通过减法来避免加法的上溢。

然后是一类比较特殊的用法:求二叉搜索树的众数和最小绝对差。看起来没啥关系,其实是一类的,都依赖于当前值的上下文,因为二叉搜索树的中序遍历是有序的。假如在数组的语境下,比如说求一个有序数组的众数,第一反应肯定是弄一个计数器,每次遇到不一样的数就清空,然后找出最大的数,大概像这样(如果众数不止一个,都返回):

vector<int> findModeInArray(vector<int> &arr)
{
    vector<int> mode;
    int max_count = 0;
    int cur_count = 1;
    int length = arr.size();
    for (int i = 1; i < length; ++i)
    {
        cur_count = arr[i] == arr[i - 1] ? cur_count + 1 : 1;

        if (cur_count == max_count)
        {
            mode.push_back(arr[i]);
        }
        else if (cur_count > max_count)
        {
            mode.clear();
            mode.push_back(arr[i]);
            max_count = cur_count;
        }
    }
    return mode;
}

如果放到BST的语境下,也是一样的,就是多了一个“翻译”的过程。而且,由于需要递归,需要通过函数的参数来保存当时的上下文。如果使用全局变量,可能会出现全局变量被意外修改的情况。解法来自junstat@LeetCode:

void inOrder(TreeNode* root, TreeNode*& pre, int& curTimes, 
             int& maxTimes, vector<int>& res){
    if (!root) return;
    inOrder(root->left, pre, curTimes, maxTimes, res);
    if (pre)
        curTimes = (root->val == pre->val) ? curTimes + 1 : 1;
    if (curTimes == maxTimes)
        res.push_back(root->val);
    else if (curTimes > maxTimes){
        res.clear();
        res.push_back(root->val);
        maxTimes = curTimes;
    }
    pre = root;
    inOrder(root->right, pre, curTimes, maxTimes, res);
}
vector<int> findMode(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    TreeNode* pre = NULL;
    int curTimes = 1, maxTimes = 0;
    inOrder(root, pre, curTimes, maxTimes, res);
    return res;
}

可以看到,几乎是完全一致的,唯一的区别在于,数组语境下使用的是for循环来进行遍历,而在BST语境下使用的是递归的中序遍历,然后把每次遍历用到的数据放在了参数里(有点闭包的意思)。

然后是BST的最小绝对差。因为是有序的,最小的绝对差必然在相邻的两个元素之间产生。放在数组语境下,就是每次用后一个减前一个,然后找到差的最小值,没什么可说的;放在BST语境下,也差不多是这样:

void inOrderTraverse(TreeNode *root, TreeNode *&pre, int &min_diff)
{
    if (root)
    {
        inOrderTraverse(root->left, pre, min_diff);
        if (pre)
        {
            min_diff = min(root->val - pre->val, min_diff);
        }
        pre = root;
        inOrderTraverse(root->right, pre, min_diff);
    }
}

int getMinimumDifference(TreeNode *root)
{
    TreeNode *pre = nullptr;
    int min_diff = INT_MAX; // #include <climits>
    inOrderTraverse(root, pre, min_diff);
    return min_diff;
}

后来又看到一个把BST变成累加树的题目:

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

这个稍微有点特殊,我一开始想的是中序遍历,然后用HashMap保存每个Node对应的累加值,然后再遍历一遍修改原来的树的值(我好像特别喜欢HashMap?):

unordered_map<int, int> sum_map;

void traverse(TreeNode *root)
{
    if (root)
    {
        traverse(root->left);

        for (auto &p : sum_map)
        {
            p.second += root->val;
        }
        sum_map[root->val] = root->val;

        traverse(root->right);
    }
}

void convert(TreeNode *root)
{
    if (root)
    {
        convert(root->left);
        root->val = sum_map[root->val];
        convert(root->right);
    }
}

TreeNode *convertBST(TreeNode *root)
{
    traverse(root);
    convert(root);
    return root;
}

结果跑出来220ms,人都傻了。然后看了题解,发现中序遍历还能倒着用的,当时的心情真是难以言喻:

int sum = 0;

TreeNode *convertBST(TreeNode *root)
{
    if (root)
    {
        convertBST(root->right);

        sum += root->val;
        root->val = sum;

        convertBST(root->left);
    }
    return root;
}

但是联想一下,如果是在数组语境下,大概也是这么个做法。所以,概括下来,BST的题目大概也就是这么个做法,说起来也很简单:

  1. 考虑在数组语境下的做法
  2. 递归进行中序遍历

最后补充一点,CSDN的md编辑器居然不能识别c++,只能识别cpp?

关于二叉搜索树的一些总结关于二叉搜索树的一些总结 元无心 发布了92 篇原创文章 · 获赞 108 · 访问量 3万+ 私信 关注
上一篇:leetcode 653. Two Sum IV - Input is a BST


下一篇:Hackerrank Day 23: BST Level-Order Traversal 逐层遍历