2020-06-16

LeetCode-BST相关

BST与一般二叉树的不同之处是，BST的中序遍历得到有序序列，具体说是left->root->right遍历结果是递增序列，right->root->left 的遍历结果是递减序列。根据BST的这个特点，与BST相关的问题，先遍历得到有序序列，后就是对一个有序数组的操作了。

先给出BST结点的定义：

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) {}
};

下面记录LeetCode 中的BST相关问题

530，783，230

思路一样，先遍历，后对一个有序数组操作。不细展开了。

// #530 #783 # 230 BST inOrder to get a 递增序列
class Sol530_783_230{

public:
// time: O(2*N)
	int getMinimumDifference(TreeNode* root) {
		inOrder(root);
		int minAD = INT_MAX;
		for (int i=1; i<vec.size(); i++){
			minAD = min(minAD, vec[i]-vec[i-1]);
			cout<<minAD<<endl;
		}
		return minAD;
	}

private:
	vector<int> vec;
	void inOrder(TreeNode* root){
        if (root!=NULL){
            inOrder(root->left);  // 只是进去，没有其他操作，直到进到最里层，最里层root==nullptr，所以直接return
            vec.push_back(root->val); // 上一句return后才开始执行这一句，及之后的语句。
            inOrder(root->right);
        }
    }
};

653

描述：

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

思路：仍是对有序数组的操作。

先序遍历后得到有序数组；后使用对撞指针找到一对值和为target。

实现：

class Sol653 {
public:
// time: O(2×N)
    bool findTarget(TreeNode* root, int k) {
        inOrder(root);
        int i=0;
        int j=vec.size()-1;
        while(i<j){
            if (vec[i]+vec[j]==k) return true;
            else if(vec[i]+vec[j] < k)
                i++;
            else
                j--;
        }
        return false;
    }
private:
    vector<int> vec;
    void inOrder(TreeNode* root){
        if (root!=NULL){
            inOrder(root->left);
            vec.push_back(root->val);
            inOrder(root->right);
        }
    }
};

938

描述：

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

思路：

方法一：中序遍历后得有序序列；后从头和尾设置两个指针对撞，找到两个位置，后将两位置间的元素累加得结果。

方法二：选择一种树的遍历方法，在遍历的过程中，判断每一个结点值是否在指定区间内，如果是，就累加到一个变量中。

实现方法二：

class Sol938 {

public:
    int sum=0;
    int rangeSumBST(TreeNode* root, const int L, cosnt int R) {
        dfs(root, L,R);
        return sum;
    }
    void dfs(TreeNode* root, int L, int R){
        if (root==nullptr) return;
        else{
            if (root->val>=L && root->val<=R)
                sum += root->val;
            if (root->val>L)
                dfs(root->left, L,R);
            if (root->val<R)
                dfs(root->right, L,R);
        }
    }
};

注意-有返回值的递归：由于rangeSumBST()函数有返回值，若将递归实现在其中，会有问题：递归函数与其返回值不一致。什么意思？具体说是，函数是递归的，自己会调用自己，而返回值是一个最终结果，一个是过程一个是结果。可能没法处理！所以考虑将递归函数和返回值分离，其中递归函数没有返回值，如上。

701

描述：

将一个结点掺入到BST中（新节点不与原BST中结点重复），要保持BST的性质不变。BST的基本操作

思路：

分析题意，一定可以在BST的叶节点的左右子节点找到新节点的位置，将其作为这个叶节点的子节点所以递归地找到带插入结点的位置即可。

实现：


// #701 BST insert operation
class Sol701 {
public:
// 在现有的 BST 的叶节点添加新的结点
// time: O(logN)
    TreeNode* insertIntoBST(TreeNode* root, const int val) {
        // 向叶节点添加子结点
        if (root==nullptr){
			return new TreeNode(val);
		}
		if (root->val == val)
			cout<<"Not going to happen"<<endl;
		else if(root->val > val){
			root->left = insertIntoBST(root->left, val);
		}else
			root->right = insertIntoBST(root->right, val);
		return root;
    }
};

注意-有返回值的递归：这个问题的返回值是节点指针TreeNode*，而递归函数每次递归的判断操作对象也是一个TreeNode*。所以这里的返回值不会影响到递归函数。所以是递归函数与其返回值一致。与上一个问题对比。

501

描述：

找到BST中出现频数最多的节点值。

思路：

第一步遍历，过程中将每个节点值放入哈希表。第二步是对哈希表的操作，找到找到频数最多的key值，可能有重复。

实现：

// #501 BST
class Sol501 {
public:
    vector<int> findMode(TreeNode* root) {
        inOrder(root)
		int secondMax = 0;
		vector<int> res;
		for (auto item: mp){
			if (item.second>secondMax){
				res.clear();
				secondMax = item.second;
			}
			if (item.second == secondMax)
				res.push_back(item.first);
		}
		return res;
            
    }
private:
	unordered_map<int, int> mp;
	void inOrder(TreeNode* root){
        if (root!=NULL){
            inOrder(root->left);
            mp[root->val]++;
            inOrder(root->right);
        }
    }
};

173

描述：

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.
hasNext() return whether we have a next smallest number

思路：

先right->root->left 遍历，得到递减序列。next()返回序列最有一个值，后删除最后一个值。hasNext()返回这个序列是否为空。

实现：

// # 173
class BSTIterator {
private:
    vector<int> nodeVal;
    void inOrder(TreeNode* root){
        if(root!=nullptr){
            inOrder(root->right);
            nodeVal.push_back(root->val);
            inOrder(root->left);
        }
    }
public:
	// time: O(N)
	// right->root->left 
    BSTIterator(TreeNode* root) {
        inOrder(root);
    }
    
    /** @return the next smallest number */
	// time: O(1)
    int next() {
        int res = nodeVal[nodeVal.size()-1];
        if (nodeVal.size()!=0)
            nodeVal.pop_back();
        return res;
    }
    
    /** @return whether we have a next smallest number */
	// time: O(1)
    bool hasNext() {
        if(nodeVal.size()!=0) return true;
        return false;
    }
};

538

描述：

BST中每个结点的值，类加上所有比这个结点大的值，得到新的二叉树。

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

思路：

先定义一个变量value=0，后进行right->root->left遍历，每遍历到一个结点，就将当前节点值累加到value，之后将更新了的value赋值给当前结点。

实现：

// #538
class Sol538 {
private:
    int value=0;
public:
// time: O(N)
    TreeNode* convertBST(TreeNode* root) {
        if (root!=nullptr){
            root->right = convertBST(root->right);
            value+=root->val;
            root->val = value;
            root->left = convertBST(root->left);
        }
        return root;
    }
};

注意-有返回值的递归

98 合法BST

描述：

判断一个BST是否合法

方法：

以left->root->right 顺序递归地判断这个树的心虚遍历是否单调递增。只要中途没有返回false，就一直递归下去，所以需要在code中所有可能返回false的情况都写出。

实现：

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* pre = NULL;
		return dfs(root, pre);
    }
private:
	bool dfs(TreeNode* root, TreeNode* &preValue){
        // 递归终止
		if (!root) return true;
        // 情况1. 返回false
		if (!dfs(root->left, preValue))
            return false;
        // 情况2. 返回false
		if (preValue && preValue->val>= root->val )
            return false;
        preValue = root;
			
		return dfs(root->right, preValue);
	}
};

如果上述逻辑不能马上写出，可以先实现一个判断单调递增链表的递归实现：

class Solution_list{
public:
	bool func(ListNode* head){
		ListNode* pre = nullptr;
		return isGreaterThanPre(head, pre);
	}
    // pre是要被更改的
	bool isGreaterThanPre(ListNode* head, ListNode* &pre){
        // 终止条件
		if (head == nullptr) return true;

        // 返回false的情况
		if (pre && head->val<=pre->val)
			return false;
		pre = head;
		return isGreaterThanPre(head->next, pre);
	}
};

注意参数的这种表达： TreeNode* &pre和ListNode* &pre 它表示，pre这个指针所存地址中的内容是会在函数中被更改的。

449

描述：

将内存中数据序列化到磁盘，后将磁盘中的数据反序列化到内存。
应用时，反序列化后的树要与序列化前的树是同一颗树，才是这个问题的目的。

1 2	Codec codec; codec.deserialize(codec.serialize(root));

思路：

困难的是

实现：

class Codec449 {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
		preOrder(root, res);
		return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream str(data);
		queue<int> q;
		string s;
		while(str>>s)
			q.push(stoi(s));  // string to int 
		return des(q, INT_MIN, INT_MAX); 
    }
private:
	void preOrder(TreeNode* root, string& res){
		if (root==nullptr) return;
		res += to_string(root->val); // anything to string
		res += ' ';
		preOrder(root->left, res);
		preOrder(root->right, res);
	}

	TreeNode* des(queue<int>& q, int low, int hig){
		if (q.empty()) return nullptr;
		int val = q.front();
		if (val<low || val>hig) return nullptr;
		q.pop();
        // 构建一个结点和其左右子节点
		TreeNode* node = new TreeNode(val);
		node->left = des(q, low, val);
		node->right = des(q, val, hig);
		return node;
	}
}；

构建一颗树，肯定是从root开始，所以先要有root后才可以构建其左右子节点。

敲黑板注意-递归函数的返回值