验证二叉搜索树

[liuyingbin19222]

给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征：

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

• 最开始的思路是通过递归实现 ， 但是并没有通过全部测试用例:\

  
  var isValid = function (p){
  if(p.left == null && p.right == null){
      return true;
  }
  if(p.left != null || p.right != null){
      if(p.left.val >= p.val || p.right.val <= p.val){
          return false;
      }     
  }
  return isValid(p.left) && isValid(p.right);
  }

var isValidBST = function(root){ if(root == null) return true; return isValid(root.left) && isValid(root.right); }

[liuyingbin19222]

将二叉树转换为数组 ， 比较数组大小，进而判断是否符合二叉搜索树；

var tree2Arr = function(root){
    return root ? tree2Arr(root.left).concat(root.val,tree2Arr(root.right)):[];
}

var isValidBST = function(root) {
    if(root == null) return true;
    var myarr = tree2Arr(root);
    for(var i = 0 ;i < myarr.length-1;i++){
        if(myarr[i] >= myarr[i+1]){
            return false;
        }
    }
    return true;
};