您的位置: 首页  >  文章  >  [LeetCode] 98. Validate Binary Search Tree & 99.Recover Binary Search Tree

[LeetCode] 98. Validate Binary Search Tree & 99.Recover Binary Search Tree

分类: 文章 • 2022-10-06 18:01:13

本周的两道题目都是来自LeetCode。一道为难度为Medium的98题Validate Binary Search Tree，一道为难度为Hard的99题Recover Binary Search Tree。之所以将这两道题合并在一起，是因为二者的关联相似度极大，更准确的说，99题是98题的延伸，只需改动一小部分即可。二者所采用的的方法都是深度优先遍历法(DFS)中的中序遍历，与我们本周算法课所讲内容一致。这也正是我选这两道题的原因。

文章目录

98题

一、问题描述

[LeetCode] 98. Validate Binary Search Tree & 99.Recover Binary Search Tree

二、问题分析

如何判断一棵树是否为二叉搜索树(BST)？那么理所当然我们应该看看BST有什么特性。显而易见的一个特性就是一个节点的值大于其左子树任意一个节点的值，小于其右子树任意一个节点的值。但是其更重要的特性确是：BST按中序遍历得到的节点序列是一个有序的升序序列！或者说，如果用pre,post的方法分别在访问一个节点前，访问一个节点后标记这个节点，那么最终post值越大的节点的value值也一定越大。针对这个特性，我们只需DFS一遍目标树，看看每一个节点的值(记为root)是否大于它前一个被访问节点(记为prev)的值即可。注意，由于prev是上一个中序遍历的节点，因此我们应该在递归的中间位置(访问其左子树之后、访问其右子树之前)更新prev。这样算法的时间复杂度为O(n)。

三、问题求解

针对问题分析，以下是c++源代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = NULL;
        return dfs(root, prev);
    }
private:
     bool dfs(TreeNode* node, TreeNode* &prev) {
        if (!node) return true;
        if(!dfs(node->left, prev)) return false;
        if (prev && prev->val >= node->val) return false;
        prev = node;
        return dfs(node->right, prev);
    }
};

99题

一、问题描述

[LeetCode] 98. Validate Binary Search Tree & 99.Recover Binary Search Tree

二、问题分析

本题很明显是之前一道题的升级版。上一道题我们谈了如何确定一棵树是否为BST，而本题我们要找出两个出错的位置，并最终调整为BST。如何找出出错的位置呢？先看在上题的算法下什么情况会出错。显然，当本节点root的值大于中序节点遍历的上一个节点prev的值即出错。接下来再看出错的情况有哪些。1.出错的两个数相邻，比如12435。这种情况在遍历树的时候只会出错一次，即在4>3时出错，我们只需要将3,4交换。2.出错的两个数不相邻，比如14325。这种情况会出错两次，分别在4>3,3>2时出错，此时需交换的两个节点分别为第一次出错的前一个节点(4)与第二次出错的后一节点(2)。除此之外不会出现第三种情况。因此我们除了要像上个题一样，有一个prev指针记录中序遍历的前一个节点，还要额外增加p,q两个指针记录出错的两个节点。当第一次出错，p记录下prev节点,q记录下root节点(其中p节点一定是出错的节点，而q出错与否目前还不清楚)。如果只有一次出错，那么遍历完树只需交换pq即可。如果发生第二次出错，那么要更新q为第二次出错的root节点，之后再交换pq。这样做的时间复杂度为O(n),空间复杂度为O(1)。

三、问题求解

针对问题分析，以下是c++源代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *pre = NULL, *p = NULL, *q = NULL;
        dfs(root, pre, p, q);
        int temp = p->val;
        p->val = q->val;
        q->val = temp;
    }
private:
    void dfs(TreeNode* root, TreeNode* &pre, TreeNode* &p, TreeNode* &q) {
    	if (root == NULL) {
    		return ;
    	}
    	dfs(root->left, pre, p, q);
    	if (pre && pre->val > root->val) {
    		if (p == NULL) {
    			p = pre;
    			q = root;
    		}
    		else {
    			q = root;
    		}
    	}
    	pre = root;
    	dfs(root->right, pre, p, q);
    }
};

需要注意的是，p,q节点在dfs参数中的调用必须以引用的形式(&p,&q)，这样才能确保在dfs回到recoverTree时p与q的本体有被赋值。之后才能顺利交换。

相关推荐