98.验证二叉搜索树

链接：98.验证二叉搜索树
难度：Medium
标签：树、深度优先搜索、二叉搜索树、二叉树
简介：给定一个二叉树，判断其是否是一个有效的二叉搜索树。

题解 1 - java

• 编辑时间：2020-02-23
• 执行用时：334ms
• 内存消耗：41.3MB
• 编程语言：java
• 解法介绍：使用中序遍历，再进行冒泡排序，若存在排序则为非 bst。

/**
 * 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<Integer>();
	public boolean isValidBST(TreeNode root) {
		if (root == null)
			return true;
		preorder(root);
		int size = list.size();
		for (int i = 0; i < size - 1; i++)
			for (int j = 0; j < size - 1 - i; j++)
				if (list.get(j) >= list.get(j + 1))
					return false;
		return true;
	}
	public void preorder(TreeNode node) {
		if (node.left != null) {
			preorder(node.left);
		}
		list.add(node.val);
		if (node.right != null) {
			preorder(node.right);
		}
	}
}

题解 2 - typescript

• 编辑时间：2021-08-07
• 执行用时：96ms
• 内存消耗：43.1MB
• 编程语言：typescript
• 解法介绍：中序遍历。

function isValidBST(root: TreeNode | null): boolean {
  if (root === null) return true;
  const q: number[] = [];
  inorder(root);
  for (let i = 1; i < q.length; i++) if (q[i] <= q[i - 1]) return false;
  return true;
  function inorder(node: TreeNode | null): void {
    if (node === null) return;
    inorder(node.left);
    q.push(node.val);
    inorder(node.right);
  }
}