LeetCode 98验证二叉搜素树(中序遍历)&99恢复二叉搜索树

柔情只为你懂 2023-01-01 14:49 108阅读 0赞

> **微信搜一搜**：`bigsai`  
> **[大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1]**  
> 关注回复**进群**即可加入力扣打卡群，欢迎划水。近期打卡：  
> [LeetCode 92反转链表Ⅱ&93复制ip地址&94二叉树的中序遍历][LeetCode 92_93_ip_94]  
> [LeetCode 96不同的二叉搜索树&95不同的二叉搜索树Ⅱ][LeetCode 96_95]  
> [LeetCode 97交错字符串(动态规划)][LeetCode 97]

## 验证二叉搜索树 ##

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

*  节点的左子树只包含小于当前节点的数。
 *  节点的右子树只包含大于当前节点的数。
 *  所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
        2
       / \
      1   3
    输出: true

示例 2:

输入:
        5
       / \
      1   4
         / \
        3   6
    输出: false
    解释: 输入为: [5,1,4,null,null,3,6]。
         根节点的值为 5 ，但是其右子节点值为 4 。

**分析**  
二叉搜索树的中序遍历是一个递增序列，所以我们只需要进行二叉树的中序遍历查询序列是否一直有序即可。当然，如果你直接利用二叉搜索树的定义左节点<根节点<右节点的话当然也没问题。具体实现上，你可以先将中序序列求出来判断是否有序，也可直接利用一个临时存储上一个节点的值进行判断。

具体代码为：

//  public boolean isValidBST(TreeNode root) {
        
    //	  List<Integer>list=new ArrayList<Integer>();
    //	  dfs(root,list);
    //	  if(list.size()<=1)return true;
    //	  for(int i=1;i<list.size();i++)
    //	  {
        
    //		  if(list.get(i)<=list.get(i-1))
    //			  return false;
    //	  }
    //	  return true;
    //  }
    //	private void dfs(TreeNode root, List<Integer> list) {
        
    //		// TODO Auto-generated method stub
    //		if(root==null)
    //			return;
    //		dfs(root.left, list);
    //		list.add(root.val);
    //		dfs(root.right, list);
    //	}
    long pre=Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        
    	 if(root==null)
    		 return true;
    	 if(!isValidBST(root.left))
    		 return false;
    	 if(pre>=root.val)
    		 return false;
    	 pre=root.val;
    	 if(!isValidBST(root.right))
    		 return false;
    	 return true; 
      }

## 恢复二叉搜索树 ##

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]

输入：root = [1,3,null,null,2]
    输出：[3,1,null,null,2]
    解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]

输入：root = [3,1,4,null,null,2]
    输出：[2,1,4,null,null,3]
    解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

树上节点的数目在范围 [2, 1000] 内
    -2^31 <= Node.val <= 2^31 - 1

**分析：**

这题主要是需要动手画一画分析。首先它告诉本来一个二叉搜索树有两个节点的值被交换，我们知道对应一个正常的二叉搜索树它的中序排序序列是有序递增的，那么要将它们的数值进行交换。

分析一个序列`1 3 5 7 8 9 10` 假如其中的3和9进行交换次序(选择模拟的时候要么选择非常远要么选择非常更直观)那么有两段逆序，两个分别可以确定大小点。如果两个相邻交换那么仅有一段逆序对，分别是交换的两个节点。

当然在具体实现的时候你可以根据位置进行记录，一旦到达第二个逆序就可以停止。这题中序遍历上你可以直接先一次求中序序列，然后找到两个逆序，第二次再去进行交换(O(n))。当然更好的方法是一次就去把这个过程搞完，需要借助一个前驱节点去比较前一个数(O(1))。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 2]

具体代码为：

//	 public void recoverTree(TreeNode root) {
        
    //		 List<Integer>list=new ArrayList<Integer>();
    //		 dfs1(root,list);
    //		 int l=-1,lvalue=0,r=-1,rvalue=0;
    //		 for(int i=1;i<list.size();i++)
    //		 {
        
    //			 if(list.get(i)<list.get(i-1))
    //			 {
        
    //				 if(l==-1) {
        
    //					 l=i-1;
    //					 lvalue=list.get(i-1);
    //				 }
    //				 r=i;
    //				 rvalue=list.get(i); 
    //			 }
    //		 }
    //		 dfs2(root,l,lvalue,r,rvalue);
    //	 }
    //	 int index=0;
    //	private void dfs2(TreeNode root, int l, int lvalue, int r, int rvalue) {
        
    //		if(root==null)
    //			return;
    //		dfs2(root.left, l, lvalue, r, rvalue);
    //		if(index>r)
    //			return;
    //		if(index==l)
    //			root.val=rvalue;
    //		else if(index==r)
    //			root.val=lvalue;
    //		index++;
    //		dfs2(root.right, l, lvalue, r, rvalue);	
    //	}
    //	private void dfs1(TreeNode root, List<Integer> list) {
        
    //		// TODO Auto-generated method stub
    //		if(root==null)
    //			return;
    //		dfs1(root.left, list);
    //		list.add(root.val);
    //		dfs1(root.right, list);
    //		
    //	}
     public void recoverTree(TreeNode root) {
        
      
      Stack<TreeNode> q1 = new Stack();	
      TreeNode first=null;
      TreeNode second=null;
      
      TreeNode pre=new TreeNode(Integer.MIN_VALUE);
      TreeNode t=root;
    	while(!q1.isEmpty()||t!=null)
    	{
        
    		if (t!=null) {
        
    			q1.push(t);
    			t=t.left;
    		}
    		else {
        
    			t=q1.pop();
    			//中序操作
    			if(t.val<pre.val)
    			{
        
    				if(first==null)
    					first=pre;
    				else {
        
    					second=t;
    					break;//可以停止了
    				}
    				second=t;
    			}
    			pre=t;//更新下pre
    			t=t.right;
    		}
    	}
    	int team=first.val;
    	first.val=second.val;
    	second.val=team;
     }

原创不易，bigsai请你帮两件事帮忙一下:

1.  star支持一下， 您的肯定是我在平台创作的源源动力。
2.  微信搜索「**bigsai**」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

![image-20201114211553660][]

[Link 1]: https://github.com/javasmall/bigsai-algorithm
[LeetCode 92_93_ip_94]: https://bigsai.blog.csdn.net/article/details/111778579
[LeetCode 96_95]: https://bigsai.blog.csdn.net/article/details/112093545
[LeetCode 97]: https://bigsai.blog.csdn.net/article/details/112134215
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]: /images/20221120/5727d51cf0014f5ba66ed95c2d7cc7dc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]: /images/20221120/f19f3c1f481b41e3acf4ee534fc698d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 2]: /images/20221120/531addc6d0ac4ffead9a2e182d67f884.png
[image-20201114211553660]: /images/20221120/0971579d7f09463687f260966813fe28.png