二叉树系列 - 二叉搜索树 - [LeetCode] 中序遍历中利用 pre节点避免额外空间。题:Recover Binary Search Tree,Validate Binary Search Tree

时间:2022-01-05 06:15:41

二叉搜索树是常用的概念,它的定义如下:

  • 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.

我们以LeetCode上的一个例题开始。

例题一:

Given a binary tree, determine if it is a valid binary search tree (BST).

要求的函数如下:

/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode *root) {
}
};

如果对二叉搜索树不够了解,可能会在思路上犯一个错误:将current结点的值和左右孩子比较,如果满足要求(即current结点的值大于左孩子,小于右孩子),就递归调用isValidBST 验证左右孩子为根结点的子树。

这样的验证方式是不对的,因为二叉搜索树的要求是:current 结点值大于左子树所有结点值,小于右子树所有结点值。上面的验证方式只能保证左右子树的根结点满足这种要求。

一个正确的验证思路是:利用二叉搜索树中序遍历是递增序列的特点,来完成验证。

那么,如何实行呢?最简单的方法是将中序遍历结果存到一个数组中,然后从头到尾扫描一遍数组,完成验证。但这样的结法除了递归遍历所需要的O(logn)空间外,还需要 O(n)的辅助空间来做数组。有没有不需要辅助空间的办法?

这就是这篇博文被记录的目的:中序遍历中利用pre节点,来避免使用额外空间。

pre节点其实就是一个额外的TreeNode,它的作用是存储上一次遍历的结点。

TreeNode *pre = NULL;
func(cur){
func(cur -> left);
pre = cur;
func(cur -> right);
}

这道例题就可以这样解决:

class Solution {
public:
bool isValidBST(TreeNode *root) {
if(!root) return true;
if(!isValidBST(root -> left)) return false;
if(pre && pre -> val >= root -> val) return false;
pre = root;
if(!isValidBST(root -> right)) return false;
return true;
}
private:
TreeNode* pre = NULL;
};

例题二:

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

有了之前的基本思想,这道题其实就可以转化为:一个递增序列中有两个值被交换了位置,如何恢复递增序列?

我们依然可以运用上面的技巧,在二叉搜索树的遍历过程中,不停比较pre结点和current结点的值,出现 pre值比current值还大的情况,就将要交换的结点保存下来。具体存储哪两个结点作为交换节点,这个在代码的注释中解释了:如果只碰到一处比较异常,那么最后交换这两个结点的值即可;如果碰到两处比较异常,那么我们将第一次异常的pre的值和第二次异常的current值交换。

/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode *root) {
if(!root) return;
findWrongNd(root);
int temp = wnd1 -> val;
wnd1 -> val = wnd2 -> val;
wnd2 -> val = temp;
}
private:
TreeNode* wnd1 = NULL;
TreeNode* wnd2 = NULL;
TreeNode* pre = NULL; void findWrongNd(TreeNode* root){
if(!root) return;
findWrongNd(root -> left);
if(pre){
if(pre -> val > root -> val){
if(!wnd1){
wnd1 = pre; //If only one descending pair has been found, save this pair into wnd1, wnd2.
wnd2 = root;
}else{
wnd2 = root; //if second descending pair is found, swap the bigger one in first pair, with smaller one in second pair. So wnd1 does not need to be changed, wnd2 = root, because currently root's value < pre's value.
}
}
}
pre = root;
findWrongNd(root -> right);
}
};

总结:这种引入Pre指针的小技巧,虽然简单,但是可以节省空间。