Leetcode_14 天数据结构入门_day14

Posted on | Edited on | In ,
| 6k | 50 mins.

好快啊，这个要做完了。

98. Validate Binary Search Tree

Analysis

判断一棵树是否是二叉搜索树。

Code

method 1

用递归来解决这个问题的关键在于，如何判断左子树所有结点都小于根节点（对应的，右子树所有结点都大于根节点），所以，需要设置一个区间，在分别遍历左、右子树时，对应改变区间的值，一旦某个结点的值不在区间内，说明这个结点一定不满足二叉搜索树的要求。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool judge(TreeNode *root, long long lower, long long upper) {
        if(!root) return true;
        if(root->val <= lower || root->val >= upper) return false;
        return judge(root->left, lower, root->val) && judge(root->right, root->val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return judge(root, LONG_MIN, LONG_MAX);
    }
};

method 2

实际上，这个题还有一种更直接的方法，因为二叉搜索树的中序遍历序列是有序的，所以可以直接得到这棵树的序列，然后判断序列是否有序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void inorder(TreeNode *root, vector<int>& v) {
        if(!root) return;
        inorder(root->left, v);
        v.push_back(root->val);
        inorder(root->right, v);
    }
    bool isValidBST(TreeNode* root) {
        vector<int> tmp;
        inorder(root, tmp);
        for(int i = 0; i < tmp.size() - 1; i++) {
            if(tmp[i + 1] <= tmp[i]) return false;
        }
        return true;
    }
};

653. Two Sum IV - Input is a BST

Analysis

这是两数之和的第 4 代升级版吗？😂

Code

method 1

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    unordered_set<int> ht;
    bool findTarget(TreeNode* root, int k) {
        if(!root) return false;
        if(ht.find(root->val) != ht.end()) return true;
        else ht.insert(k - root->val);
        return findTarget(root->left, k) || findTarget(root->right, k);
    }
};

method 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    unordered_set<int> ht;
    bool findTarget(TreeNode* root, int k) {
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode *node = q.front(); q.pop();
            if(ht.find(node->val) != ht.end()) return true;
            ht.insert(k - node->val);
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
        return false;
    }
};

235. Lowest Common Ancestor of a Binary Search Tree

Analysis

做这个题之前，首先要明确 LCA 的概念，虽然英文是 Lowest Common Ancestor，但并不能直接理解成最小公共祖先，而是要理解成最近（最低）公共祖先。

Code

method 1

要求最近公共祖先，那得先知道祖先是什么。所以，这个问题实际上是一个求子结点路径的问题。分别得到 2 个子结点的路径后，就可以很容易的找到 2 个子结点路径中的最近公共结点了，这就是它们的最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void getpath(TreeNode *root, TreeNode *target, vector<TreeNode*>& path) {
        path.push_back(root);
        if(root == target) return;
        if(root->val > target->val) getpath(root->left, target, path);
        if(root->val < target->val) getpath(root->right, target, path);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> ppath, qpath;
        getpath(root, p, ppath);
        getpath(root, q, qpath);
        TreeNode *lca;
        int index = 0;
        while(index < ppath.size() && index < qpath.size()) {
            if(ppath[index] == qpath[index]) lca = ppath[index];
            else break;
            index++;
        }
        return lca;
    }
};

求路径的过程，也可以不用递归来做，直接根据二叉搜索树的性质来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void getpath(TreeNode *root, TreeNode *target, vector<TreeNode*>& path) {
        while(root) {
            path.push_back(root);
            if(root->val == target->val) return;
            else if(root->val > target->val) root = root->left;
            else root = root->right;
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> ppath, qpath;
        getpath(root, p, ppath);
        getpath(root, q, qpath);
        TreeNode *lca;
        int index = 0;
        while(index < ppath.size() && index < qpath.size()) {
            if(ppath[index] == qpath[index]) lca = ppath[index];
            else break;
            index++;
        }
        return lca;
    }
};

method 2

仔细想想这个问题，实际上是不需要分别求出两个子结点的路径的，可以直接一次性求 2 个结点的路径，但不是真正的求出来。如果当前结点比 2 个结点都大，就去遍历左子树；反之都小，就去遍历右子树。一旦不满足这 2 种情况，就说明这个结点是这两条路径的分岔点，那这个结点就是 LCA 了。换句话说，就是这 2 个结点的公共路径的最后一个结点就是 LCA。

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

有意思的是，p、q 这 2 个结点要么是在这个分岔点的不同子树中，要么其中一个就是这个分岔点。
有了上面的思路，递归的思路自然也有了：

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

自然，bfs 的思路也出来了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        queue<TreeNode*> qu;
        qu.push(root);
        TreeNode *lca;
        while(!qu.empty()) {
            lca = qu.front(); qu.pop();
            if(lca->val > p->val && lca->val > q->val) qu.push(lca->left);
            else if(lca->val < p->val && lca->val < q->val) qu.push(lca->right);
            else break;
        }
        return lca;
    }
};

Summary

不同的树具有不同的性质，题目是根据这些性质出的，自然也得根据这些性质来求解，题目是做不完的，所以，更多的是抓住题目的本质。

Buy me a coffee ? :)
0%