二叉树系列-二叉搜索树-[LeetCode]在中间顺序遍历中使用前置部分

二进制搜索树是一个常用的概念，其定义如下:

我们从LeetCode的示例开始.

给出一个二叉树，确定它是否是有效的二叉搜索树（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) {
    }
};

如果您对二进制搜索树的了解不足二叉排序树中序遍历，则可能会犯一个错误的想法: 如果满足要求，则将当前节点的值与左右子节点进行比较（即，该值当前节点的大于左子节点，小于右子节点），则递归调用isValidBST以验证左右子节点是否是子树的根节点.

这种验证方法是错误的，因为二进制搜索树的要求是: 当前节点的值大于左侧子树中所有节点的值，并且小于右侧子树中所有节点的值. 以上验证方法只能保证左右子树的根节点满足此要求.

正确的验证想法是使用二叉搜索树中的顺序遍历功能作为增量序列来完成验证.

那么，它如何工作？最简单的方法是将中阶遍历的结果存储在数组中，然后从头到尾扫描数组以完成验证. 但是，除了递归遍历所需的O（logn）空间外，此方法还需要数组的O（n）辅助空间. 有没有不需要辅助空间的方法？

这是此博客文章的目的: 在中间顺序遍历中使用前置节点，以避免使用多余的空间.

前置节点实际上是一个附加的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;
};

二元搜索树（BST）的两个元素被错误交换.

在不更改其结构的情况下恢复树.

使用先前的基本思想，这个问题实际上可以转换为: 交换递增顺序中的两个值，如何恢复递增顺序？

我们仍然可以使用上述技术. 在遍历二叉搜索树期间，我们不断比较前节点和当前节点的值. 如果pre值大于当前值二叉排序树中序遍历，则要交换的节点单击Save. 哪两个节点专门存储为交换节点？在代码注释中对此进行了解释: 如果仅异常遇到一个比较，则最后可以交换这两个节点的值;如果遇到两次比较，则我们将第一个异常的前值与第二个异常的当前值交换.

/**
 * 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指针的这一小技巧虽然简单，但却可以节省空间.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-204942-1.html