[数据结构与算法]LeetCode Day 3 二叉搜索树

二叉搜索树的概念

二叉搜索树满足以下的性质：

• 可以为空树
• 若左子树不为空，则左子树上的所有节点的值小于根节点的值
• 若右子树不为空，则右子树上的所有节点的值大于根节点的值
• 左右子树均为二叉搜索树

由上述定义可以得知：将二叉搜索树进行中序遍历，得到的将是升序数组

将升序数组转换为高度平衡二叉搜索树

将升序数组转换为高度平衡的二叉搜索树，需要用递归的方式实现。由于高度平衡，因此每次需要将排在中间位置的元素作为根节点，左右两端数组分别再构造二叉搜索树。递归代码如下所示：

struct TreeNode* toBST(int* nums, int left, int right) {
    // 返回条件
    if (left > right) {
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    int midIndex = (left + right) / 2;
    root->val = nums[midIndex];
    // 构建左子树
    root->left = toBST(nums, left, midIndex - 1);
    // 构建右子树
    root->right = toBST(nums, midIndex + 1, right);
    return root;
}

struct TreeNode* sortedArrayToBST(int* nums, int numsSize){
    return toBST(nums, 0, numsSize - 1);
}

将升序链表转换为高度平衡二叉搜索树

顺序表转换为二叉搜索树的常规思想都是先找到中间节点，再两边分治地构建子树。然而，链表转换为二叉搜索树的难点在于如何找到中间节点，常见的方法有暴力遍历以及快慢指针。这里先介绍一种利用二叉树中序遍历的特点的递归实现，其思想是：

• 遍历链表，得到链表中的元素个数n
• 设置全局变量node，初始值为链表的头结点head
• 从0~n-1，自上而下地模拟二叉树递归的过程：（1）当左边界>右边界时，返回空节点NULL；（2）否则，先对左半区间调用该递归函数，生成左子树；再初始化一个树节点，将node指向的值赋予当前树节点的值，把所生成的左子树挂载到当前节点的左孩子；接着把全局变量node向后移动到它的后继节点，；最后对右半区间调用该递归函数，生成右子树，把所生成的右子树挂载到当前节点的右孩子。（可以看到这个过程和中序遍历的过程是一致的）
• 自下而上来看，由于递归函数的特性，编译器自动帮我们维护了一棵递归树，而由于我们设计的递归函数是符合中序遍历的，且链表从左到右的顺序恰好是二叉搜索树的中序遍历。因此最后生成的二叉搜索树是符合条件的。（高度平衡是由二分递归来保证的）。

代码实现如下：

struct ListNode* node;

struct TreeNode* toBST(int left, int right){
    if (left > right) {
        return NULL;
    }
    struct TreeNode* leftNode = toBST(left, (left + right) / 2 - 1);
    struct TreeNode* treeNode = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    treeNode->val = node->val;
    node = node->next;
    treeNode->left = leftNode;
    treeNode->right = toBST((left + right) / 2 + 1, right);
    return treeNode;
}

struct TreeNode* sortedListToBST(struct ListNode* head){
    struct ListNode* p = head;
    int n = 0;
    while (p) {
        n++;
        p = p->next;
    }
    node = head;
    return toBST(0, n - 1);
}

检查二叉搜索树的正确性

题目描述：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

（1）节点的左子树只包含 小于 当前节点的数。
（2）节点的右子树只包含 大于 当前节点的数。
（3）所有左子树和右子树自身必须也是二叉搜索树。

思路：（1）递归思想：根据二叉搜索树本身的特点，递归地给每个节点确定上下界，若不符合该上下界，则有误。（2）利用二叉搜索树的中序遍历是升序数组这一特点，将BST进行中序遍历，若不符合升序，则有误。

下面给出递归方法的代码实现：

bool isValidBSTHelper(struct TreeNode* root, int min, int max, bool minValid, bool maxValid) {
    if (!root) {
        return true;
    }
    bool nodeValBool = true;
    if (minValid) {
        nodeValBool &= (root->val > min);
    }
    if (maxValid) {
        nodeValBool &= (root->val < max);
    }
    return isValidBSTHelper(root->left, min, root->val, minValid, true) && isValidBSTHelper(root->right, root->val, max, true, maxValid) && nodeValBool;
}

bool isValidBST(struct TreeNode* root){
    return isValidBSTHelper(root, -2147483648, 2147483647, false, false);
}

恢复二叉搜索树

题目描述：

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

思路：利用二叉搜索树的中序遍历是升序数组这一特点。将有误的BST进行中序遍历，找出其中不符合升序的节点，将它们的值进行交换即可。

代码如下：

void recoverTree(struct TreeNode* root){
    int* mark = (int*) malloc(2 * sizeof(int));
    int intIdx = 0;
    struct TreeNode** nodes = (struct TreeNode**) malloc(1000 * sizeof (struct TreeNode*));
    int idx = 0;
    struct TreeNode** stk = (struct TreeNode**) malloc(1000 * sizeof (struct TreeNode*));
    int top = 0;
    struct TreeNode* cur = root;
    // 中序遍历 
    while (top > 0 || cur) {
        while (cur) {
            stk[top++] = cur;
            cur = cur->left;
        }
        cur = stk[--top];
        // 记录要交换的节点
        if (idx > 0) {
            if (cur->val < nodes[idx-1]->val) {
                if (intIdx == 0) {
                    mark[intIdx++] = idx - 1; 
                } else {
                    mark[intIdx++] = idx;
                }
            }
        }
        nodes[idx++] = cur;
        cur = cur->right;
    }
    struct TreeNode* n1;
    struct TreeNode* n2;
    if (intIdx == 1) {
        n1 = nodes[mark[0]];
        n2 = nodes[mark[0] + 1];
    } else {
        n1 = nodes[mark[0]];
        n2 = nodes[mark[1]];
    }
    int temp = n2->val;
    n2->val = n1->val;
    n1->val = temp;
}