二叉搜索树

二叉搜索树

定义

二叉排序树又称二叉查找树（二叉搜索树），它或是一棵空的二叉树，或是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有节点的值均小于根节点的值
若它的右子树不空，则右子树上所有节点的值均大于根节点的值
它的左右子树也都是二叉排序树

性质

若二叉搜索树为平衡二叉树， 高度为logN + 1, 查找效率为： O(logN)
若非平衡，查找效率可能退化为O(N)
空间复杂度: O(N)
『借助二叉排序树进行搜索，但因为所建立的树本身不一定是轴对称的，所以每次比较并不能确保减小一半范围。』
二叉树的存储要求：需要树形结构，相比顺序存储需要占用更多的空间，但也有链接型数据结构灵活可拓展的有点。

二叉搜索树遍历

offer54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

与下面的[LC230]相似, 基本做法：中序遍历得到数组，然后直接取即可，需要注意遍历顺序
- 求第K大，right -> root -> left方式进行遍历，相应第K个元素即为目标值
在逆中序遍历中，进行计数操作，当到第K个元素直接进行结果记录
- 亿点细节：提前结束递归方式： if (K==0) return;

class Solution {
public:
    int ans = 0;
    int K;
    void dfs(TreeNode* root) {
        // right -> root -> left
        if (root == nullptr) return;
        dfs(root -> right); 
        if (K == 0) return; // 提前剪枝 提高算法效率
        K--;
        if (K == 0) {
            ans = root -> val;
        }
        cout << " "<< K << " " << root -> val << endl;
        dfs(root -> left);
    }

    int kthLargest(TreeNode* root, int k) {
        K = k;
        cout << K << endl;
        dfs(root);
        return ans;
    }
};

230. 二叉搜索树BST中第K小的元素 [Medium]

基本做法：遍历整颗树，然后从结果中取值

class Solution {
public:
    vector<int> res;
    void inorder(TreeNode* root) {
        if (!root) {
            return;
        }
        inorder(root -> left);
        res.push_back(root -> val);
        inorder(root -> right);
    }
    int kthSmallest(TreeNode* root, int k) {
        inorder(root);
        if (k > res.size()) {
            return res[res.size() - 1];
        }
        return res[k - 1];
    }
};

也可以基于stack进行迭代式遍历，减少遍历次数
关键点： 中序遍历的迭代写法

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        
        stack<TreeNode*> st;
        int count = 0;
        int res = 0;
        while (root || !st.empty()) {
            while (root) {
                st.push(root);
                root = root -> left;
            }
            root = st.top();
            st.pop();
            count++;
            if (count == k) {
                return root -> val;
            }
            root = root -> right;
        }
        return res;
    }
};

代码优化：

class Solution {
public:
    int ans = 0;
    int K;
    void dfs(TreeNode* root) {
        if (root == nullptr) return;
        dfs(root -> left);
        if (K == 0) return;
        K--;
        if (K == 0) {
            ans = root -> val;
        }
        dfs(root -> right);
    }
    int kthSmallest(TreeNode* root, int k) {
        K = k;
        dfs(root);
        return ans;
    }
};

二叉搜索树性质的利用

主要利用二叉搜索树的中序遍历有序性以及root left right的有序关系进行问题求解和优化

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

进行分类排列：
- 考虑左子树、根和右子树的节点分配：对于4个节点
- 那么分配比例可以是：

dp[n] = $\sum_{0} dp[i] * dp[n-i-1]$
dp[0] = 1, dp[1] = 1

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <=n ; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += (dp[j] * dp[i - j - 1]);
            }
        }
        return dp[n];
    }
};

98. 验证二叉搜索树 [*]

涉及基本的二叉树遍历以及二叉搜索树性质
递归解法:
- 利用BST所有左子树节点小于根节点，所有右子树节点大于根节点，这一性质构建递归公式
关键点： 构造比较方式，确定lower higher参数

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper){
        if(root==NULL) return true;

        if(root->val<=lower||root->val>=upper){
            return false;
        }
        return helper(root->left,lower,root->val)&&helper(root->right,root->val,upper);

    }
    bool isValidBST(TreeNode* root) {
        return helper(root,LONG_MIN,LONG_MAX);
        }
};

遍历解法：利用中序遍历得到BST对应的数组，检查是否是单增的数组即可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> nodes;
    // 中序遍历
    void inOrderParse(TreeNode* root){
        if(root==NULL) return;
        inOrderParse(root->left);
        nodes.push_back(root->val);
        inOrderParse(root->right);
    }
    bool isValidBST(TreeNode* root) {
        inOrderParse(root);
        for(int i=0;i<nodes.size()-1;i++){
            if(nodes[i+1]<=nodes[i]){
                return false;
            }
        }
        return true;
        }
      
};

基于中序遍历的迭代方式进行实现

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        int flag = 0;
        int prev = 0;
        while (!st.empty() || root != nullptr) {
            while(root) {
                st.push(root);
                root = root -> left;
            }
            root = st.top();
            st.pop();
            int cur = root -> val;
            
            if (flag > 0 && cur <= prev) {
                return false;
            }
            flag = 1;
            prev = cur;
            root = root -> right;
        }
        return true;

    }
};

剑指33. 二叉搜索树的后序遍历序列判断 [Medium]

给出一颗树的后序遍历列表，判断是否为二叉搜索树
考察对BST的特性理解，根据后序遍历的顺序 L R root，可以确定root节点位置
- 每次先搜索所有小于root节点的区间，即得到左子树区域
- 然后分析剩下的右子树部分是否都满足大于等于根节点的要求
- 递归地对左右两个区域继续进行判断
- helper(left, mid-1) helper(mid, right-1)

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        return helper(postorder, 0, postorder.size() - 1);
    }
    bool helper(vector<int>& postorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int mid = left;
        // 寻找左子树部分
        while (postorder[mid] < postorder[right]) {
            mid++;
        }
        int tmp = mid;
        // 对右子树部分进行扫描，确认是否存在非法情况 
        // 细节： tmp < right
        while (tmp < right) {
            if (postorder[tmp++] < postorder[right]) 
                {
                    return false;
                }
        }
        //  细节： right-1
        return helper(postorder, left, mid - 1) && helper(postorder, mid, right - 1);
    }
};

单调栈解法
时间复杂度 O(N) 空间复杂度 O(N)
- 初始化：单调栈 stackstack ，父节点值 root = +\infinroot=+∞ （初始值为正无穷大，可把树的根节点看为此无穷大节点的左孩子）；
- 倒序遍历 postorderpostorder ：记每个节点为 r_i
  - 判断：若 r_i>root，说明此后序遍历序列不满足二叉搜索树定义，直接返回 false ；
  - 更新父节点 root ：当栈不为空且 r_i<stack.peek() 时，循环执行出栈，并将出栈节点赋给 rootroot 。
  - 入栈：将当前节点 r_i入栈；
- 若遍历完成，则说明后序遍历满足二叉搜索树定义，返回 true。

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        stack<int> st;
        int root = INT_MAX;
        for (int i = postorder.size() - 1; i >= 0; i--) {
            int cur = postorder[i];
            while (!st.empty() && st.top() > cur) {
                root = st.top();
                st.pop();
            }
            if (cur > root) {
                return false;
            }
            st.push(cur);
        }
        return true;
    }
};

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

根据二叉搜索树的特性，可以先判断两个目标节点的分布情况：
- 都位于同一子树：递归到子树中再判断
- 分别位于左/右子树：直接返回当前root节点即可
当然也可以采用与[LC236.]的通用写法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 在同一侧进行递归搜索
        while (root != nullptr && (root -> val - p -> val) * (root -> val - q -> val) > 0) {
            root = (root -> val - p -> val) > 0 ? root -> left : root -> right;
        } 
        return root;
    }
};

530. 二叉搜索树的最小绝对差

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值

由于二叉搜索树的特殊性，本题本质上需要从中序遍历中相邻节点值的差值中找出最小的一个
- 二叉搜索树的中序遍历为有序数组，那么可以在遍历中进行差值计算，并进行结果更新
关键点： 中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = INT_MAX;
    int prev = -1;
    void getDist(TreeNode* root) {
        if (!root) return;
        getDist(root -> left);
        if (prev == -1) {
            prev = root -> val;
        }
        else {
            ans = min(ans, root -> val - prev);
            prev = root -> val;
        }
        getDist(root -> right);
    }
    int getMinimumDifference(TreeNode* root) {
        getDist(root);
        return ans;
    }
};

二叉搜索树的构建

108. 有序数组转搜索二叉树 [KEY]

要求左右子树高度平衡，即需要选择数组中间位置的数字作为根节点当数组长度为奇数或者偶数时，存在差异：对于偶数时需要考虑选择偏左位置还是偏右位置的作为根节点，两者没有效果差异
通过递归形式，进行转换

class Solution {
public:
    TreeNode * helper(vector<int>& nums, int left,int right){
        if(left>right){
            return NULL; 
        }
        int mid=int((left+right+1)/2);

        TreeNode * root=new TreeNode(nums[mid]);
        root->left=helper(nums,left,mid-1);
        root->right=helper(nums,mid+1,right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums,0,nums.size()-1);

    }
};

109. 有序链表转换为二叉搜索树

给定有序升序单向链表，构建高度平衡二叉搜索树

与[LC108.]基本相似，差异在于堆有序链表如何处理，如何寻找中点，然后再进行后续递归呢？
- 通过快慢指针，进行中点确定
- 并考虑到后续分段递归的链表情况，需要将中点节点从原链表中隔开
- 并考虑对于长度为1的链表的特殊情况，避免陷入死循环： head != mid
关键点： 有序链表的中点确定

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    ListNode* findMid(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* prev = nullptr;
        while (fast != nullptr && fast -> next != nullptr) {
            fast = fast -> next -> next;
            prev = slow;
            slow = slow -> next;
        }
        if (prev != nullptr)
            prev -> next = nullptr;
        return slow;
    }
    TreeNode* sortedListToBST(ListNode* head) {
        if (head == nullptr) return nullptr;
        ListNode* mid = findMid(head);
        TreeNode* root = new TreeNode(mid -> val);
        if (head != mid) { // 终止递归的重要条件
            root -> left = sortedListToBST(head);
            root -> right = sortedListToBST(mid -> next);
        }
        return root;
    }
};

二叉搜索树的增/删/改

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

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

经典的二叉树删除问题，考虑二叉搜索树的特性
关键点在于删除节点后如何替换节点，
- 可以使用右子树的最小节点替代当前root： 搜索子树的最小值，然后再在右子树进行删除操作
- 或者使用左子树的最大节点替代当前root：搜索子树的最大值，然后再在左子树进行删除操作
关键点： 替代操作

class Solution {
public:
    int getMin(TreeNode* root) {
        if (!root) return INT_MAX;
        return min(root -> val, min(getMin(root -> left), getMin(root -> right)));
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;
        // 删除的情况
        if (root -> val == key) {
            if (!root -> left && !root -> right) {
                return nullptr;
            }
            if (!root -> left) {
                return root -> right;
            }
            if (!root -> right) {
                return root -> left;
            }
            // 使用右子树的最小值来替代删除节点 或者 使用左子树的最大值来替代
            int minVal = getMin(root -> right);
            root -> val = minVal;
            // 递归删除后面要替换的节点 key = minVal; 
            root -> right = deleteNode(root -> right, minVal);
        }
        else if (root -> val < key) {
            root -> right = deleteNode(root -> right, key);
        }
        else {
            root -> left = deleteNode(root -> left, key);
        }
        return root;
    }
};

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

输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

与二叉搜索树的删除相比，插入操作相对比较简单
本质上利用BST的节点大小性质，自顶而下进行遍历，寻找插入方向；在叶子节点位置创建节点完成插入

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) {
            return new TreeNode(val);
        }
        if (root -> val > val) {
            // 往左子树插入
            root -> left = insertIntoBST(root -> left, val);

        }
        else {
            // 往右子树插入
            root -> right = insertIntoBST(root -> right, val);
        }
        return root;
    }
};

99. 恢复二叉搜索树

给定二叉搜索树， 树中两个节点被错误交换。 在不改变结构的情况下，恢复这颗树。

只需定位错误节点位置即可，存在两种情况：
- 相邻的两个节点错误交换 [1, 2 ,3 ,4 ] => [1, 3, 2, 4]
- 非相邻的两个节点交换
通过遍历有序数组即可得到对应的错误节点, 然后进行节点值交换即可
本质上分两步：
- 1. 遍历得到有序数组
- 1. 线性遍历有序数组确定错误节点，进行交换
时间复杂度 O(N) 空间复杂度 O(N)
关键点： 异常节点判断 morris遍历与普通递归遍历

class Solution {
public:
    vector<TreeNode*> nodes;
    void inorder(TreeNode* root) {
        if (!root) return;
        inorder(root -> left);
        nodes.push_back(root);
        inorder(root -> right);
    }

    void recoverTree(TreeNode* root) {
        if (!root) return;
        inorder(root);
        TreeNode* x = nullptr;
        TreeNode* y = nullptr;
        for (int i = 0; i < nodes.size() - 1; i++) {
            if (nodes[i] -> val > nodes[i+1] -> val) {
                y = nodes[i + 1];
                if (x == nullptr) {
                    x = nodes[i];
                }
            }
        }
        if (x != nullptr && y != nullptr) {
            swap(x -> val, y -> val);
        }
    }
};

进一步，我们可以通过递归的方式，省掉显式取数组的空间
- 但递归的方式仍然涉及到递归栈空间，不是真正的常数级空间
- 常数级空间还得看morris

class Solution {
public:
    TreeNode* pre = nullptr;
    void inorder(TreeNode* root, TreeNode* &x, TreeNode* &y) {
        if (!root) return;
        inorder(root -> left, x, y);
        if (pre != nullptr) {
            if (pre -> val > root -> val) {
                if (x == nullptr) {
                    x = pre;
                }
                y = root;
            }
        }
        pre = root;
        inorder(root -> right, x, y);

    }
    void recoverTree(TreeNode* root) {
        if (!root) return;
        TreeNode* x = nullptr;
        TreeNode* y = nullptr;
        inorder(root, x, y);
        if (x != nullptr && y != nullptr) {
            swap(x -> val, y -> val);
        }
    }
};

如何实现常数级别的算法？
- Morris遍历（莫里斯遍历）利用叶子节点的空指针进行指针调整，避免使用栈结构，实现常数级空间的遍历
- Morris遍历主要逻辑：
  - 寻找左子树的最右节点(叶子节点)，将最右节点right指向root
  - 相当于进行方向线索设置
  - 为了避免进行循环，还要进行循环控制
- 空间复杂度 O(1)

class Solution {
public:
    void recoverTree(TreeNode* root) {
        if (!root) return;
        TreeNode* x = nullptr;
        TreeNode* y = nullptr;
        TreeNode* pre = nullptr;
        
        // morris 遍历
        while (root != nullptr) {
            TreeNode* tmp = root -> left;
            if (tmp != nullptr) {
                // 避免进入循环 
                while (tmp -> right && tmp -> right != root) {
                    tmp = tmp -> right;
                }
                // 子树右节点为空 进行root连接
                if (tmp -> right == nullptr) {
                    tmp -> right = root;
                    root = root -> left;
                }
                else {
                    // 进行异常节点记录  morris遍历之外的逻辑
                    if (pre != nullptr && pre -> val > root -> val) {
                        y = root;
                        if (x == nullptr) {
                            x = pre;
                        }
                    }
                    pre = root;

                    // 出现循环情况
                    tmp -> right = nullptr;
                    root = root -> right; // 进入右子树
                }
            }
            else {
                if (pre != nullptr && pre -> val > root -> val) {
                    y = root;
                    if (x == nullptr) {
                        x = pre;
                    }
                }
                pre = root;
                root = root -> right; // 没有左节点 就访问左节点
            }
        }
        if (x != nullptr && y != nullptr) {
            swap(x -> val, y -> val);
        }
    }
};

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

T7-二叉搜索树.md

T7-二叉搜索树.md

二叉搜索树

定义

性质

二叉搜索树遍历

offer54. 二叉搜索树的第k大节点

230. 二叉搜索树BST中第K小的元素 [Medium]

二叉搜索树性质的利用

96. 不同的二叉搜索树

98. 验证二叉搜索树 [*]

剑指33. 二叉搜索树的后序遍历序列判断 [Medium]

235. 二叉搜索树的最近公共祖先

530. 二叉搜索树的最小绝对差

二叉搜索树的构建

108. 有序数组转搜索二叉树 [KEY]

109. 有序链表转换为二叉搜索树

二叉搜索树的增/删/改

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

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

99. 恢复二叉搜索树

Files

T7-二叉搜索树.md

Latest commit

History

T7-二叉搜索树.md

File metadata and controls

二叉搜索树

定义

性质

二叉搜索树遍历

offer54. 二叉搜索树的第k大节点

230. 二叉搜索树BST中第K小的元素 [Medium]

二叉搜索树性质的利用

96. 不同的二叉搜索树

98. 验证二叉搜索树 [*]

剑指33. 二叉搜索树的后序遍历序列判断 [Medium]

235. 二叉搜索树的最近公共祖先

530. 二叉搜索树的最小绝对差

二叉搜索树的构建

108. 有序数组转搜索二叉树 [KEY]

109. 有序链表转换为二叉搜索树

二叉搜索树的增/删/改

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

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

99. 恢复二叉搜索树