面试题 04.05. 合法二叉搜索树

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例 1:

输入:
    2
   / 
  1   3
输出: true

示例 2:

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

简单好理解的做法：

中序遍历。后放入list中。克隆list， 排序list,如果list,和clone中的对象 相同位置元素 不相等就不合法，全部相等就合法。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {

         helper(root);
         //中序后，正确的结果是从小到大的排序，否则list中有乱序就是错的.
          ArrayList<Integer> clone = (ArrayList<Integer>) list.clone();
          Collections.sort(list);
          for(int i = 0; i< list.size();i++)
          {
              int a = list.get(i);
              int b = clone.get(i);
              if(a!=b)
              return false;
          }
          return true;       
    }

    public void helper(TreeNode root)
    {
       if(root == null)  return ;
       helper(root.left);
       list.add(root.val);
       helper(root.right);
    }
}

 递归法:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
       return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper)
    {
        if(node == null)
        {
            return true;
        }
        if(node.val <= lower || node.val >= upper)
        {
            return false;
        }

        return isValidBST(node.left ,lower, node.val) &&  isValidBST(node.right, node.val, upper);

    }

}