Tag Archives: BST

LeetCode Contains Duplicate III

LeetCode Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.


给定一个数组,问是否存在两个相距k之内的差的绝对值在t之内的数。
这个题有点难度,是LeetCode Contains Duplicate II的升级版。
首先,要求距离在k之内,所以想到维护一个长度为k的滑动窗口,在这个滑动窗口内判断是否有差的绝对值在t之内的两个数。
具体参考讨论区。用一个set来保存长度为k的滑动窗口window,每次往前滑动一格,如果窗口大于k了,则删除窗口左边的元素。对于即将进入窗口的数nums[i],我们需要判断窗口内是否存在一个x,使得|x-nums[i]|\leq t,展开就是nums[i]-t\leq x\leq t+nums[i]
由于set内部是有序的树结构,所以可以用set.lower_bound直接判断大于等于nums[i]-t的数x是否在window中。如果在的话,我们再判断是否满足x\leq t+nums[i],这个式子等价于x-nums[i]\leq t,为什么要这么写呢,因为nums[i]有可能是INT_MAX或者INT_MIN,为了防止溢出,需要把相关的操作数转换为long long。
完整代码如下:

typedef long long ll;
class Solution {
public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
		set<ll> window;
		for (int i = 0; i < nums.size(); ++i) {
			if (i > k)window.erase(nums[i - k - 1]); // 删除窗口左边的元素
			auto it = window.lower_bound(ll(nums[i]) - t); // x>=nums[i]-t
			if (it != window.end() && *it - nums[i] <= t)return true; // x<=nums[i]+t
			window.insert(nums[i]);
		}
		return false;
	}
};

本代码提交AC,用时19MS。

LeetCode Kth Smallest Element in a BST

LeetCode Kth Smallest Element in a BST
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Hint:

  1. Try to utilize the property of a BST.
  2. What if you could modify the BST node's structure?
  3. The optimal runtime complexity is O(height of BST).

给定一棵二叉搜索树,问树中第k小的元素是哪个。
因为BST的特点是左<=根<=右,所以对树中序遍历之后就得到升序序列,取出第k个元素即可。代码如下:

class Solution {
private:
	void inOrder(TreeNode* root, int& k, int& target) {
		if (k < 0)return;
		if (root->left)inOrder(root->left, k, target);
		--k;
		if (k == 0)target = root->val;
		if (root->right)inOrder(root->right, k, target);
	}
public:
	int kthSmallest(TreeNode* root, int k) {
		int target;
		inOrder(root, k, target);
		return target;
	}
};

本代码提交AC,用时26MS,时间复杂度是O(k)。
Follow up指出如果可以修改节点,怎样才能使得复杂度降低到O(height of tree),可以给每个节点增加一个属性rank:左子树节点个数,该属性的含义就是小于该节点的节点个数,也即当前节点在中序遍历中的位置(rank)。查找的过程就类似二分了,从根节点开始,如果k小于当前节点的rank,说明第k小的数在左子树;如果k大于当前节点的rank,说明第k小的数在右子树;如果k==rank,则当前节点就是第k小的数。这样的查找过程就是不断的在当前节点选择走左子树还是右子树,走过的节点最多是树的高度。
rank属性可以在建BST时完成。

LeetCode Convert BST to Greater Tree

LeetCode Convert BST to Greater Tree
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:

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

给定一棵二叉搜索树,要求把每个点的值换成BST中大于等于该点的其他所有点的值之和。
很有意思的一个题,因为BST满足左<=根<=右,则比某个点大的点在其根节点和右兄弟上,为了得到根节点和右兄弟节点之和,可以采用右->根->左的遍历顺序,也就是和先序遍历正好相反的顺序遍历BST,同时记录遍历过的数之和。
代码如下:

class Solution {
private:
	void revPreOrder(TreeNode* root, int& sum) {
		if (root->right)revPreOrder(root->right, sum);
		sum += root->val;
		root->val = sum;
		if (root->left)revPreOrder(root->left, sum);
	}
public:
	TreeNode* convertBST(TreeNode* root) {
		if (!root)return NULL;
		int sum = 0;
		revPreOrder(root, sum);
		return root;
	}
};

本代码提交AC,用时46MS。

LeetCode Minimum Absolute Difference in BST

LeetCode Minimum Absolute Difference in BST
Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.
Example:

Input:
   1
    \
     3
    /
   2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.


求一棵二叉搜索树中任意两个节点数值之差的绝对值的最小值。
因为是BST,所以满足左子树<=根节点<=右子树。以根节点root为例,则最小的差可能有两个,一个是root减去左子树中的最大数,另一个是右子树中的最小数减去root,所以整体的最小值就是这两个最小值的最小值。
左子树中的最大数就是左子树中最右下端的叶子节点,右子树中的最小数就是右子树中最左下端的叶子节点。
然后递归的以左右孩子为根更新最小值。代码如下:

class Solution {
public:
	int getMinimumDifference(TreeNode* root) {
		int l = INT_MIN, r = INT_MAX;
		int left_min = INT_MAX, right_min = INT_MAX;
		if (root->left) {
			TreeNode* left = root->left;
			while (left->right)left = left->right;
			left_min = min(root->val - left->val, getMinimumDifference(root->left));
		}
		if (root->right) {
			TreeNode* right = root->right;
			while (right->left)right = right->left;
			right_min = min(right->val - root->val, getMinimumDifference(root->right));
		}
		return min(left_min, right_min);
	}
};

本代码提交AC,用时19MS。
还有一种思路,因为是BST,所以其中序遍历的结果是升序的,得到有序数组之后,相邻两个数的差的最小值就是要求的结果。
实际上,我们可以不用完整求出其升序序列之后再计算差,只需要在每次中序遍历时,记住该节点的上一个节点,这样该节点的值减去上一节点的值就相当于有序数组中相邻两个数作差。
代码如下:

class Solution {
private:
	long long m_nLast, m_nAns;
	void inorderTraverse(TreeNode* root) {
		if (!root)return;
		inorderTraverse(root->left); // 左
		m_nAns = min(m_nAns, root->val - m_nLast);
		m_nLast = root->val; // 根
		inorderTraverse(root->right); // 右
	}
public:
	Solution() {
		m_nLast = INT_MIN;
		m_nAns = INT_MAX;
	}
	int getMinimumDifference(TreeNode* root) {
		inorderTraverse(root);
		return m_nAns;
	}
};

本代码提交AC,用时16MS。注意因为可能出现x-INT_MIN导致int溢出,所以两个成员变量定义为long long。
参考:http://bookshadow.com/weblog/2017/02/26/leetcode-minimum-absolute-difference-in-bst/

LeetCode Delete Node in a BST

LeetCode Delete Node in a BST
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.
  2. If the node is found, delete the node.

Note: Time complexity should be O(height of tree).
Example:

root = [5,3,6,2,4,null,7]
key = 3
    5
   / \
  3   6
 / \   \
2   4   7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
    5
   / \
  4   6
 /     \
2       7
Another valid answer is [5,2,6,null,4,null,7].
    5
   / \
  2   6
   \   \
    4   7

从二叉搜索树中删除一个节点,并返回一个新的二叉搜索树;如果该节点不存在,则返回原二叉搜索树。
因为是BST,所以很容易找到等于value的节点,问题的关键是怎样删除这个节点,并且保持二叉搜索树的特性:左孩子<根节点<右孩子。
如果要删除的节点的左子树为空,则删除该节点,返回该节点的右子树即可;类似的,如果要删除的节点的右子树为空,则删除该节点,返回该节点的左子树。
难点就是当该节点的左子树和右子树都不为空时,该怎么处理。如下图,假设我们找到了root的值等于key,则需要删除root节点,并调整其子树使满足BST的性质。

       root
      /    \
   left  right
  /   \  /   \
 x    l r     y

具体有两种方案,题目中也举了例子,即可以把left放到root的位置,或者把right放到root的位置。
现在假设要把left放到root的位置,则需要处理left的右子树l。l肯定要被切下来,又l比left大,所以l应该接在right子树,具体位置是接在right子树的最小节点上,即right的最左下端的叶子节点r。也就是变成下面这样:

    left            right
    /  \            /   \
   x               r     y
                  /
                 l 

最后把right子树接在left右子树即可:

            left
            /  \
           x    right
                /   \
               r     y
              /
             l  

知道了调整的思路,代码就好写了:

class Solution {
private:
	TreeNode* justify(TreeNode *root) {
		if (root->left == NULL || root->right == NULL)return root->left == NULL ? root->right : root->left;
		TreeNode *left = root->left, *right = root->right;
		TreeNode *l = left->right, *r = right;
		while (r->left) r = r->left;
		r->left = l;
		left->right = right;
		return left;
	}
public:
	TreeNode* deleteNode(TreeNode* root, int key) {
		TreeNode *dummy = new TreeNode(-1), *pre = dummy, *child = root;
		dummy->right = root;
		while (child != NULL && child->val != key) {
			pre = child;
			if (key < child->val) child = child->left;
			else child = child->right;
		}
		if (child == NULL)return dummy->right;
		if (pre->left == child)pre->left = justify(child);
		else pre->right = justify(child);
		return dummy->right;
	}
};

本代码提交AC,用时33MS。
如果要把right放到root的位置,思路是类似的,需要把right的左子树切下来接到left最右下端的叶子节点上。
参考:https://segmentfault.com/a/1190000005032508

LeetCode Validate Binary Search Tree

LeetCode Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

    2
   / \
  1   3

Binary tree [2,1,3], return true.
Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.


验证一棵二叉树是否是二叉搜索树。二叉搜索树树需要满足左孩子小于等于根节点,根节点小于等于右孩子,本题中是严格的小于关系,所以二叉搜索树的中序遍历是严格递增的。一种解法是对二叉树中序遍历,然后检查遍历结果是否是严格递增的,这种解法很简单,不赘述了。
另外一种解法是直接用递归判断,代码如下。我们在每一次递归时,都判断当前节点是否大于最小值,且小于最大值,同时把当前节点的值递归带入。代码中没有求min和max的过程,但是每次调用的时候能正确检查,里面的奥秘需要自己体会,不太好讲。
举个例子吧,下图中节点6违反了BST的规则,虽然13所在子树是BST,但是6小于根节点10,所以不是BST。本代码是怎样判断出来的呢,首先根节点传入右孩子的约束是[10,max],15传入左孩子的约束是[10,15],13传入左孩子的约束是[10,13],所以6并不属于[10,13],不属于BST。

    10
   / \
  5   15
     /  \
    13   20
   /  \
  6   14
class Solution {
public:
	bool helper(TreeNode* root, long long minVal, long long maxVal) {
		if (root == NULL)return true;
		if (root->val <= minVal || root->val >= maxVal)return false;
		return helper(root->left, minVal, root->val) && helper(root->right, root->val, maxVal);
	}
	bool isValidBST(TreeNode* root) {
		long long minVal = LLONG_MIN, maxVal = LLONG_MAX	;
		return helper(root, minVal, maxVal);
	}
};

本代码提交AC,用时13MS。

LeetCode Find Mode in Binary Search Tree

LeetCode Find Mode in Binary Search Tree
Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.
Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node's key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
  • Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

   1
    \
     2
    /
   2

return [2].
Note: If a tree has more than one mode, you can return them in any order.
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).


找到二叉搜索树中所有的众数,如果有多个众数,都要给出。并且Follow up限制空间复杂度为O(1)。
很有意思的一个题,如果把二叉搜索树当成一棵普通的树,并且没有O(1)空间复杂度的限制,则在遍历时,可以使用hash统计每个数出现的频率,然后取最高频率的数。代码如下:

class Solution {
public:
	void work(unordered_map<int, int>& hash, TreeNode* root, int& modCnt) {
		if (root == NULL)return;
		++hash[root->val];
		modCnt = max(modCnt, hash[root->val]);
		work(hash, root->left, modCnt);
		work(hash, root->right, modCnt);
	}
	vector<int> findMode(TreeNode* root) {
		unordered_map<int, int> hash;
		int modCnt = INT_MIN;
		work(hash, root, modCnt);
		vector<int> ans;
		unordered_map<int, int>::iterator it = hash.begin();
		while (it != hash.end()) {
			if (it->second == modCnt)ans.push_back(it->first);
			++it;
		}
		return ans;
	}
};

本代码提交AC,用时25MS。
如果使用二叉搜索树的特点并且考虑O(1)的空间复杂度,就有点复杂了。因为二叉搜索树的左孩子小于等于根节点,根节点小于等于右孩子,所以如果对二叉搜索树中序遍历的话,得到的序列就是一个非递减序列,也就是说是一个有序序列,那就好办多了。比如给定序列[1,2,2,3,4,4,5,6],要找出数组中的众数,并且限制O(1)空间复杂度,应该就不难了。
因为要O(1)空间复杂度,就不能用hash统计频率了,因为众数可能有多个,我们没法在一次遍历时就既找到最大的频率,又找到众数,所以可以采取两次遍历的策略。第一遍先找到最大的频率,上面的例子中是2(2和4都出现了两次);第二遍再把频率等于2的数值找出来,就是众数了。
对应到二叉搜索树中,就是对树中序遍历两次,第一次得到最大的频率以及众数的个数,第二遍再把所有众数都找出来。代码如下:

class Solution {
private:
	vector<int> mods;
	int curVal = 0, curCnt = 0, modCnt = 0, maxCnt = 0;
	void handleValue(int v) {
		if (v != curVal) {
			curVal = v;
			curCnt = 0;
		}
		++curCnt;
		if (curCnt > maxCnt) { // 第二次遍历时不会走此分支
			maxCnt = curCnt;
			modCnt = 1;
		}
		else if (curCnt == maxCnt) {
			if (!mods.empty())mods[modCnt] = curVal;
			++modCnt;
		}
	}
	void inorder(TreeNode* root) {
		if (root == NULL)return;
		inorder(root->left);
		handleValue(root->val);
		inorder(root->right);
	}
public:
	vector<int> findMode(TreeNode* root) {
		inorder(root);
		mods.resize(modCnt);
		curCnt = 0;
		modCnt = 0;
		inorder(root);
		return mods;
	}
};

本代码提交AC,用时19MS。
参考:https://discuss.leetcode.com/topic/77335/proper-o-1-space

LeetCode Serialize and Deserialize BST

LeetCode Serialize and Deserialize BST
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.


本题要序列化和反序列化二叉搜索树。因为二叉搜索树属于二叉树,所以可以直接用LeetCode Serialize and Deserialize Binary Tree对普通二叉树的序列化和反序列化方法。但是二叉搜索树又有其特殊性,即左孩子小于等于根节点,根节点小于等于右孩子。所以如果知道树中有哪些数,通过插入的方法就可以构造好二叉搜索树。
首先还是根据层次遍历或者树的先序遍历得到树的序列化表示,那么序列化的第一个数就是根节点了。反序列化时,依次插入后续的节点构成一棵二叉搜索树就好了。但是数值插入的顺序不能乱,比如下图,虽然确定了根节点是1,如果先插入了4号节点,再插入3号节点,则反序列化得到的树就不是原来的树了。为了保证序列化到的数值顺序正确,可以使用层次遍历或者树的先序遍历。

完整代码如下:

class Codec {
public:
	// Encodes a tree to a single string.
	string serialize(TreeNode* root) {
		if (root == NULL)return "";
		string ans = to_string(root->val);
		if (root->left) ans += ","+serialize(root->left);
		if (root->right) ans += ","+serialize(root->right);
		return ans;
	}
	void insert(TreeNode* root, TreeNode* node) {
		if (node->val < root->val) {
			if (root->left == NULL)root->left = node;
			else insert(root->left, node);
		}
		else {
			if (root->right == NULL)root->right = node;
			else insert(root->right, node);
		}
	}
	// Decodes your encoded data to tree.
	TreeNode* deserialize(string data) {
		if (data == "")return NULL;
		TreeNode* root = NULL;
		for (int start = 0, end = 0; end <= data.size(); ++end) {
			if (data[end] == ',' || end == data.size()) {
				TreeNode* node = new TreeNode(atoi(data.substr(start, end - start).c_str()));
				if (root == NULL)root = node;
				else insert(root, node);
				start = end + 1;
			}
		}
		return root;
	}
};

本代码提交AC,用时26MS。

LeetCode Lowest Common Ancestor of a Binary Search Tree

LeetCode Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.


给定一棵二叉搜索树和两个节点,问这两个节点的最近公共祖先(LCA)。LCA问题很久以前在hihoCoder上做过好多,用到一些比较高级的算法。
这个题的一个特点是二叉树是二叉搜索树,二叉搜索树的特点是左孩子小于等于根节点,根节点小于等于右孩子。不失一般性,令p<=q,所以如果p<=root<=q,则p,q分立root两边,则root就是p,q的LCA。如果p,q都小于root,则递归在root->left找。如果p,q都大于root,则递归在root->right找。
递归的算法很容易就实现了,代码如下:

class Solution {
public:
	TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
		if (p->val > q->val)swap(p, q);
		if (p->val <= root->val&&q->val >= root->val)return root;
		if (p->val < root->val&&q->val < root->val)return lowestCommonAncestor(root->left, p, q);
		if (p->val > root->val&&q->val>root->val)return lowestCommonAncestor(root->right, p, q);
	}
};

本代码提交AC,用时32MS。