leetcode—Validate Binary Search Tree

leetcode—Validate Binary Search Tree

描述：

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

Assume a BST is defined as follows:

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

   

  confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

  
  OJ's Binary Tree Serialization:

  The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

  Here's an example:

     1
    / \
   2   3
      /
     4
      \
       5
  

  The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

   

  思路：

  由於二叉排序樹和對二叉樹的中序遍歷所形成的值是有序的是充分必要條件，所以僅需對二叉樹進行中序遍歷即可，並將遍歷的結點的值存儲到一個list中，然後依次比較list中的值，是有序的則二叉樹為二叉排序樹，否則則不是。

  當然，一個更好的方法是用一個temp暫存上一個結點的值，然後依次進行比較即可。

  代碼：

   

  public boolean isValidBST(TreeNode root) {
  		boolean flag=true;
  		Listlist=new ArrayList();
  	     if(root==null)
  			 return flag;
  	     Stackst=new Stack();
  	     st.push(root);
  	     TreeNode top=null;
  	     while(!st.empty())
  	     {
  	    	 top=st.peek();
  	    	 while(top.left!=null)
  	    	 {
  	    		 st.push(top.left);
  	    		 top=top.left;
  	    	 }
  	    	 while(top.right==null)
  	    	 {
  	    		 list.add(top.val);
  	    		 st.pop();
  	    		 if(!st.empty())
  	    			 top=st.peek();
  	    		 else
  	    			 break;
  	    	 }
  	    	 if(!st.empty())
  	    	 {
  	    		 list.add(top.val);
  		    	 st.pop();
  		    	 st.push(top.right);
  	    	 }
  	    	 
  	     }
  	     int len=list.size();
  	     int num=list.get(0),temp=0;
  	     for(int i=1;itemp)
  	    	 {
  	    		 flag=false;
  	    		 break;
  	    	 }
  	    	 num=temp;
  	     }
  		return flag;
      }

   

  結果：