性质

unique-binary-search-trees

给一个数字n,试着计算以这个[1,n]为root的bst有多少独一无二的。

这是一个数学题目，其中和catalan数密切相关。catalan数有很多种应用场景，值得总结一把。

f(0) = 0;
令f(0) = 1
f(1) = f(0)*f(0)
f(2) = f(1)*f(0) + f(0)*f(1)
f(3) = f(2)*f(0) + f(1)*f(1) + f(0)*f(2)
……
f(n) = f(n-1)*f(0) + f(n-2)*f(1) +……f(0)*f(n-1)
Copy

由此得出规律，

对于任意以i为根节点的二叉树，

其左子树的值一定小于i，也就是[0, i - 1]区间，

而右子树的值一定大于i，也就是[i + 1, n]区间。

假设左子树有m种排列方式，而右子树有n种，则对于i为根节点的二叉树总的排列方式就是m x n

参考资料: https://www.cnblogs.com/liuliu5151/p/9108838.html

则代码如下:

class Solution {
public:
    int numTrees(int n) {
        int a[n + 1];
        a[0] = a[1] = 1;
        for(int i = 2; i <=n; i++){
            a[i] = 0;
            for (int j = 0; j < i; j++)
                a[i] += a[j] * a[i-j-1]; // 这一步尤其精妙
        }
        return a[n];
    }
};
Copy

700. search in a BST

Search in a Binary Search Tree

这道题目是给你一个BST，然后另外给定一个值，判断这个值是否在BST中，如果在的话，返回以这个值为root的子树，否则返回null。期初吧，我想的是应该可能需要栈什么的操作，憋了半天，实在没什么好的办法，参考下其他人的答案吧，不丢人的。

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
       while(root != nullptr && root->val != val){
           root = (root->val > val) ? (root->left) : (root->right);
       }
        return root;
    }
};
Copy

要么就说，好的程序员价值连城呢，如果放到古代，这种人都得是杨过郭靖这类的大侠，像我这种，都得是不配给台词的小罗罗。

653. Two Sum IV - Input is a BST

这道题目还是比较有意思的，原因在于使用另一个数据结构保存树中的某一节点，我当时想到过这个问题就是不知道运用什么方法解决妥当：考虑过 BST,让root值不停的与k（或者差进行比较），但是呢，这样很大的问题就是你不确定怎么不遗漏。原来，你像使用下面的set容器，就可以解决这个问题还可以确定一点的是： set就是一个hashtable.

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> set;
        return dfs(root, set, k);

    }
    bool dfs(TreeNode* root, unordered_set<int>& set, int k){
        if(root == NULL) return false;
        if(set.count(k - root->val)) return true;
        set.insert(root->val);
        return dfs(root->left, set, k) || dfs(root->right, set, k);
    }
};
Copy

leetcode binary-search-tree

性质

unique-binary-search-trees

700. search in a BST

653. Two Sum IV - Input is a BST

Comments