LeetCode日志(二)

发表于 | 分类于 |
字数统计: 244 | 阅读时长 ≈ 1

二叉搜索树BST

修剪二叉搜索树

669. 修剪二叉搜索树
题意，只保留值在 L ~ R 之间的节点。
用递归做，如果当前结点大于上界，则修剪左子树。
如果当前结点小于下界，则修建右子树。
否则两颗子树都要修剪。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if(root == NULL)
            return root;
        if(root -> val > R)
            return trimBST(root -> left, L, R);
        if(root -> val < L)
            return trimBST(root -> right, L, R);
        root -> left = trimBST(root -> left, L, R);
        root -> right = trimBST(root -> right, L, R);
        return root;
    }
};

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

235. 二叉搜索树的最近公共祖先
利用BST的特点来进行寻找。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int val = root -> val, l = p -> val, r = q -> val;
        if(val > l && val > r)
            return lowestCommonAncestor(root -> left, p, q);
        if(val < l && val < r)
            return lowestCommonAncestor(root -> right, p, q);
        return root;
    }
};