Leetcode--Validate Binary Search Tree

Problem Description:

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 <code>"{1,#,2,3}"</code> means? 

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:

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

解法一：

二叉搜尋樹定義為或者是一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 它的左、右子樹也分别為二叉排序樹。

是以直接采用周遊判斷的方法，每次找到該節點左子樹的最大值和右子樹的最小值與目前節點比較，不滿足條件則不是，滿足再判斷左右子樹是否都滿足條件。該解法最壞情況複雜度為O（n^2)。（最壞情況為所有結點都在一邊的時候）

代碼如下：

解法二：

利用二叉搜尋樹中序周遊有序遞增的性質，在中序周遊的過程中判斷左子樹、目前節點和右子樹是否滿足條件，時間複雜度為O(n)。