[LeetCode] 98. Validate Binary Search Tree

轉自LeetCode

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.

Example 1:

    2
   / \
  1   3

Binary tree [2,1,3], return true.

Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.

<Solution>

這題要來確認 input 給的 BST 是不是符合規則的

看個例子

       5
     /   \
    3     8
   / \   / \
  0   4 6  10

先注意到一點，題目規範的 BST 是不會有重複元素出現的，只有大於小於，沒有等於的問題

因此，可以用 inorder traversal 來歷遍每個 node，並檢查是否符合遞增數列的走向

因為每個 subtree 都也要符合題目BST的規則，所以用 inorder traversal 來看，output會是一個遞增數列

0 3 4 5 6 8 10

code 如下(參考資料)

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isValidBST(TreeNode* root) {
	//> use inorder to traverse BST
	//> the output should be increasing order
	vector<int> prevNum;
	TreeNode *curr = root;
	stack<TreeNode *> nodeStack;
	while(curr || !nodeStack.empty()) {
	while(curr) {
	nodeStack.push(curr);
	curr = curr->left;
	}
	curr = nodeStack.top();
	nodeStack.pop();
	if(prevNum.empty()) {
	prevNum.push_back(curr->val);
	}
	else {
	//> must in increasing order
	if(curr->val <= prevNum[0]) {
	return false;
	}
	else {
	prevNum[0] = curr->val;
	}
	}
	curr = curr->right;
	}
	return true;
	}
	};

view raw validBinarySearchTree_1.cpp hosted with ❤ by GitHub

這題理論上是可以用 morris traversal 的，但在 LeetCode 的環境跑，一直都會有 run time error

看到別人也有遇到同樣問題，所以就先放棄 morris traversal 的解法

這邊還有一種想法，是利用 BST 的本質，就是 left node < root node < right node

利用這個本質特性，搭配遞迴去檢查 left subtree 和 right subtree，來看整個 tree 是否是合法的 BST

這邊使用 long 來存放最大最小值，是為了包含 int 的最大最小值的邊界檢查

code 如下
c++

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	bool isValidBST(TreeNode* root) {
	return checkValidBST(root, LONG_MIN, LONG_MAX);
	}
	bool checkValidBST(TreeNode *root, const long &minVal, const long &maxVal) {
	if(!root) {
	return true;
	}
	else if(root->val <= minVal || root->val >= maxVal) {
	return false;
	}
	//> check left subtree and right subtree
	return checkValidBST(root->left, minVal, root->val) && checkValidBST(root->right, root->val, maxVal);
	}
	};

view raw validBinarySearchTree_2.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var ti = TreeNode(5)
	* var v = ti.`val`
	* Definition for a binary tree node.
	* class TreeNode(var `val`: Int) {
	* var left: TreeNode? = null
	* var right: TreeNode? = null
	* }
	*/
	class Solution {
	fun isValidBST(root: TreeNode?): Boolean {
	return valid(root, Long.MIN_VALUE, Long.MAX_VALUE)
	}
	fun valid(node: TreeNode?, minValue: Long, maxValue: Long): Boolean {
	return when {
	node == null -> true
	node!!.`val` <= minValue || node!!.`val` >= maxValue -> false
	else -> {
	valid(node!!.left, minValue, node!!.`val`.toLong())
	&& valid(node!!.right, node!!.`val`.toLong(), maxValue)
	}
	}
	}
	}

view raw validate_binary_search_tree.kt hosted with ❤ by GitHub