leetcode98 验证二叉搜索树

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

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

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

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

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

思路：任意中序遍历，是按顺序的就是二叉搜索树（性质）

我是morris遍历

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for a binary tree node.
     
    
   

    

     

    
    

     

       * public class TreeNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * TreeNode left;
     
    
   

    

     

    
    

     

       * TreeNode right;
     
    
   

    

     

    
    

     

       * TreeNode(int x) { val = x; }
     
    
   

    

     

    
    

     

       * }
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
	public static boolean isValidBST(TreeNode head) {
     
    
   

    

     

    
    

     
		if (head == null) {
     
    
   

    

     

    
    

     
			return true;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		boolean res = true;
     
    
   

    

     

    
    

     

      		TreeNode pre = null;
     
    
   

    

     

    
    

     

      		TreeNode cur1 = head;
     
    
   

    

     

    
    

     

      		TreeNode cur2 = null;
     
    
   

    

     

    
    

     
		while (cur1 != null) {
     
    
   

    

     

    
    

     

      			cur2 = cur1.left;
     
    
   

    

     

    
    

     
			if (cur2 != null) {
     
    
   

    

     

    
    

     
 while (cur2.right != null && cur2.right != cur1) {
     
    
   

    

     

    
    

     

       cur2 = cur2.right;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if (cur2.right == null) {
     
    
   

    

     

    
    

     

       cur2.right = cur1;
     
    
   

    

     

    
    

     

       cur1 = cur1.left;
     
    
   

    

     

    
    

     
 continue;
     
    
   

    

     

    
    

     

       } else {
     
    
   

    

     

    
    

     

       cur2.right = null;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			if (pre != null && pre.val >= cur1.val) {
     
    
   

    

     

    
    

     

       res = false;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      			pre = cur1;
     
    
   

    

     

    
    

     

      			cur1 = cur1.right;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		return res;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103458514