[Golang][Leetcode][BinaryTree]刷題系列-98-Validate Binary Search Tree

Contents
98. Validate Binary Search Tree
Level : Medium
原題連結 : Click
題目 :
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid 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.
Example :
Note
Example 1:
Input: root = [2,1,3] Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node’s value is 5 but its right child’s value is 4.
解題思路 :
- 這題考察的是你對於Binary Search Tree特性的掌握度
- 基本的特性我就不贅述了,這邊講一個大家比較會忽略掉的特性: 當BST進行inorder排序時,必然是由小到大的有序排列
- 換言之,我們也可以用此特性去檢查BST,若它的Inorder排序並非由小到大也就代表它不符合BST
- 以下提供兩個解法,一個是利用BST定義去完成的解法,另一個是利用inorder特性去完成的解法
Recursive解法-1
- time complexity: O(n) , space complexity: O(1)
Runtime: 4 ms, faster than 95.20% of Go online submissions for Validate Binary Search Tree.
|
|
Recursive解法-2-利用Inorder特性
- time complexity: O(n) , space complexity: O(1)
|
|
最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!