二叉搜索树

发表于 | 分类于 ， ， |

验证二叉搜索树、二叉搜索树中第k小的元素、把二叉搜索树转换为累加树、二叉搜索树中的搜索、二叉搜索树中的插入操作、删除二叉搜索树中的节点、不同的二叉搜索树 I、不同的二叉搜索树 II

BST的遍历框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 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) {}
 * };
 */
void BST(TreeNode* root, int target){
    if(root->val == target){
        //找到目标，做点什么
    }
    if(root->val < target){
        BST(root->right, target);
    }
    if(root->val > target){
        BST(root->left, target);
    }
}

98.验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return helper(root, nullptr, nullptr);
    }
    //借助辅助函数，給所有子树节点添加一个 min 和 max 边界
    bool helper(TreeNode* root, TreeNode* min, TreeNode* max){
        if(root==nullptr) return true;
        
        if(min!=nullptr && root->val<=min->val) return false;
        if(max!=nullptr && root->val>=max->val) return false;

        return helper(root->left, min, root) && helper(root->right, root, max);
    }
};

230.二叉搜索树中第k小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        //思路：利用二叉搜索树中序遍历性质

        traverse(root, k);
        return res;
    }
    int res=0; //记录结果
    int rank=0; //记录排名
    void traverse(TreeNode* root, int k){
        if(root==nullptr) return;

        traverse(root->left, k);

        //中序
        rank++;
        if(rank==k){
            //找多第k小的元素
            res=root->val;
        }

        traverse(root->right, k);
    }
};

538.把二叉搜索树转换为累加树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        //思路：利用二叉搜索树中序遍历性质，
        //为求大于等于当前节点的和，先遍历右子树，再根节点，后左子树

        traverse(root);
        return root;
    }
    int sum=0; //记录累加和
    void traverse(TreeNode* root){
        if(root==nullptr) return;

        traverse(root->right);

        sum += root->val; //维护累加和
        root->val = sum; //转化成累加树

        traverse(root->left);
    }
};

700.二叉搜索树中的搜索

1
2
3
4
5
6
7
8
9
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root==nullptr) return nullptr;
        if(root->val > val) return searchBST(root->left, val);
        if(root->val < val) return searchBST(root->right, val);
        return root;
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        //找到空位置插入新节点
        if(root==nullptr){
            TreeNode* root = new TreeNode(val);
            return root;
        }
        //val 大，则插到右子树上面
        if(root->val < val){
            root->right = insertIntoBST(root->right, val);
        }
        //val 小，则插到左子树上面
        if(root->val > val){
            root->left = insertIntoBST(root->left, val);
        }
        return root;
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr) return nullptr;
        if(root->val==key){
            //恰好是末端节点, 直接删除
            if(root->left==nullptr && root->right==nullptr) return nullptr;

            //只有一个非空子节点，删除之后要让他的孩子节点接替他的位置
            if(root->left==nullptr) return root->right;
            if(root->right==nullptr) return root->left;

            //有两个非空子节点， 必须找到左子树最大的节点或者右子树最小的节点来接替
            //这里选择右子树最小的节点

            //找到右子树最小的节点
            TreeNode* minNode = getMin(root->right);
            //将root改成minNode
            root->val = minNode->val;
            //转而去删除 minNode
            root->right = deleteNode(root->right, minNode->val);
        }else if(root->val > key){
            root->left = deleteNode(root->left, key);
        }else if(root->val < key){
            root->right = deleteNode(root->right, key);
        }
        return root;
    }
    TreeNode* getMin(TreeNode* node){
        //BST最左边的就是最小的
        while(node->left!=nullptr) node=node->left;
        return node;
    }
};

剑指offer 36.二叉搜索树与双向链表

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* pre=NULL; //用于保存中序遍历的前一个节点
    Node* head=NULL; //用于记录排序链表的头节点
    Node* treeToDoublyList(Node* root) {
        if(root==NULL) return root;
        dfs(root);
        
        //连接首尾
        head->left = pre;
        pre->right = head;
        
        return head;
    }
    void dfs(Node* root){
        //base case
        if(root==NULL) return;
        // 遍历左子树
        dfs(root->left);

        /*中序遍历位置*/
        if(pre!=NULL) pre->right = root; //将前驱节点的右指针指向当前根节点
        else head = root; //保存链表头节点
        root->left = pre; //root的left指针指向其前驱
        pre = root; //前驱节点右移
         
        // 遍历右子树
        dfs(root->right);
    }
};

96.不同的二叉搜索树 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numTrees(int n) {
        // dp[i]表示i个节点组成的不同二叉排序树的总数
        // dp[n] = dp[0] * dp[i - 1] + dp[1] * dp[i - 2] 
        // + dp[2] * d[i - 3] + ... + dp[i - 1] * dp[0];

        vector<int> dp(n+1);

        //base case
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
};

95.不同的二叉搜索树 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        //思路：
        //遍历不同的节点并使其作为根节点
        //构建左右子树+根节点
        //构成一颗完整的树

        return build(1, n);
        
    }
    vector<TreeNode*> build(int low, int high){
        vector<TreeNode*> res;
        if(low > high){
            res.push_back(nullptr);
            return res;
        }
        //遍历每一个节点作为根节点
        for(int i=low;i<=high;i++){
            //构建左右子树
            vector<TreeNode*> left = build(low, i-1);
            vector<TreeNode*> right = build(i+1, high);
            //遍历左右子树，再利用上根节点[i]来构建完整的树
            for(TreeNode* leftNode : left){
                for(TreeNode* rightNode : right){
                    TreeNode* root = new TreeNode(i);
                    root->left = leftNode;
                    root->right = rightNode;
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};

剑指offer 68-I 二叉搜索树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val<p->val && root->val<q->val){
            return lowestCommonAncestor(root->right, p, q);
        }
        if(root->val>p->val && root->val>q->val){
            return lowestCommonAncestor(root->left, p, q);
        }
        return root;
    }
};
-------------本文结束 感谢阅读-------------
0%