您好,登錄后才能下訂單哦!
小編給大家分享一下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.
解法一:
遞歸思想,遞歸先序遍歷,假定當(dāng)前結(jié)點(diǎn)為root,其左子樹(shù)右下角節(jié)點(diǎn)為pre,右子樹(shù)左下角節(jié)點(diǎn)為next
情況一:root==NULL,return true
情況二:
root!=NULL,則判斷,
a)如果有左孩子,則如果root->left->val>=root->val ,則返回false;
b)如果比左子樹(shù)中右下角元素小,return false;
c)如果有右孩子,即如果root->right->val<=root->val,則返回false;
d)如果比右子樹(shù)左下角大,即如果next->val<=root->val,return false;
如果a,b,c,d都不為真,則說(shuō)明,當(dāng)前節(jié)點(diǎn)值比左孩子大,且比其前序節(jié)點(diǎn)值大,比右孩子小,且比后續(xù)節(jié)點(diǎn)值小,這時(shí)返回左子樹(shù)和右子樹(shù)的結(jié)果。
即
最后return BST(root->left)&&BST(root->right)
TreeNode* findpre(TreeNode *root){ if(!root||!root->left) return NULL; TreeNode *p=root->left; while(p->right){ p=p->right; } return p; } TreeNode* findnext(TreeNode *root){ if(!root||!root->right) return NULL; TreeNode *p=root->right; while(p->left){ p=p->left; } return p; } bool isValidBST(TreeNode* root) { if(!root) return true; if(root->left&&root->left->val>=root->val) return false; if(root->right&&root->right->val<=root->val) return false; TreeNode *pre=findpre(root),*next=findnext(root); if(pre&&pre->val>=root->val||next&&next->val<=root->val) return false; return isValidBST(root->left)&&isValidBST(root->right); }
解法二:
從解法一看出,其實(shí)只要保證,當(dāng)前值比左子樹(shù)pre節(jié)點(diǎn)大,且比右子樹(shù)next節(jié)點(diǎn)值小即可,可以把a(bǔ),b,這兩種情況注釋掉,但存在也是有一定用處的,可以首先判斷左右孩子,如果左右孩子都不滿(mǎn)足,則就不用找前序和后繼了。
bool isValidBST(TreeNode* root) { if(!root) return true; /*if(root->left&&root->left->val>=root->val) return false; if(root->right&&root->right->val<=root->val) return false;*/ TreeNode *pre=findpre(root),*next=findnext(root); if(pre&&pre->val>=root->val||next&&next->val<=root->val) return false; return isValidBST(root->left)&&isValidBST(root->right); }
解法三:
其實(shí),利用中序遍歷可以得到有序序列,只要當(dāng)前節(jié)點(diǎn)比前一個(gè)節(jié)點(diǎn)大,即是BST,
bool isValidBSTCore(TreeNode *root,TreeNode *&pre){ if(!root) return true; if(!isValidBSTCore(root->left,pre))//左子樹(shù) return false; if(pre&&pre->val>=root->val)//當(dāng)前結(jié)點(diǎn)與前節(jié)點(diǎn)比較 return false; pre=root;//修改pre return isValidBSTCore(root->right,pre);//右子樹(shù) } bool isValidBST(TreeNode* root) { if(!root) return true; TreeNode *pre=NULL; return isValidBSTCore(root,pre); }
看完了這篇文章,相信你對(duì)“Validate Binary Search Tree的示例分析”有了一定的了解,如果想了解更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道,感謝各位的閱讀!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。