leetcode의 Validate Binary Search Tree

Validate Binary Search Tree
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  "{1,#,2,3}"  means? > read more on how binary tree is serialized on OJ. 방법1: 두 갈래 찾기 트리의 순서가 점차 증가하는 서열의 특징에 따라 순서를 진행할 때 어떤 노드의 값이 그의 순서 노드보다 큰 것을 발견하면 불법이다.
class Solution {
public:
    bool isValidBST(TreeNode* root,TreeNode*& pre) {
    	if(!root)return true;
    	bool flag = isValidBST(root->left,pre);
    	if(!flag)return false;
    	if(pre && pre->val >= root->val)return false;
    	pre = root;
    	return isValidBST(root->right,pre);
    }
    
    bool isValidBST(TreeNode* root)
    {
    	TreeNode* pre = NULL;
    	return isValidBST(root,pre);
    }
};

방법2: 두 갈래 찾기 트리의 정의에 따라 각 노드는 좌우 트리 값의 중간에 있기 때문에 매번 반복할 때마다 하나의 값의 범위를 정한다. 이 범위는 현재 트리 값의 두 경계이다. 이 범위로 합법성을 판단하면 이 방법의 효율은 방법보다 높다.
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool isValidBST(TreeNode* root,int minValue,int maxValue)// 
    {
    	if(!root)return true;
    	if(minValue < root->val && root -> val < maxValue)
    	{
    		return isValidBST(root->left,minValue,root->val) && isValidBST(root->right,root->val,maxValue);
    	}
    	return false;
    }
    bool isValidBST(TreeNode* root)
    {
    	return isValidBST(root,INT_MIN,INT_MAX);
    }
};

좋은 웹페이지 즐겨찾기