溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
本篇文章給大家分享的是有關(guān)如何理解大數(shù)據(jù)中二叉搜索樹的后序遍歷序列，小編覺得挺實用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷結(jié)果。如果是則返回 true，否則返回 false。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。
參考以下這顆二叉搜索樹：
5
/ \
2 6
/ \
1 3示例 1：
輸入: [1,6,3,2,5]
輸出: false示例 2：
輸入: [1,3,2,6,5]
輸出: true提示：
數(shù)組長度 <= 1000
解題思路：
1，后續(xù)遍歷的特點［左子樹｜右子樹｜根］
2，所以最后一個元素一定是根節(jié)點
3，從左往后遍歷，找到第一個比根元素大的元素，從這個位置將數(shù)組拆成左右子數(shù)
4，判斷右邊子樹，如果有元素比根元素大，那么不符合二叉搜索樹的性質(zhì)
5，遞歸遍歷，直到葉子節(jié)點
6，對于這類題目是兒叉樹和后續(xù)遍歷的一個結(jié)合，主要考核對二叉樹的理解
代碼實現(xiàn)：
func verifyPostorder(postorder []int) bool { if len(postorder)<=1{ return true } root:=postorder[len(postorder)-1] fmt.Println(root,postorder) right:=0; for right<len(postorder)&&postorder[right]<root{ right++ } for i:=right;i<len(postorder);i++{ if postorder[i]<root{ return false } } return verifyPostorder(postorder[:right])&&verifyPostorder(postorder[right:len(postorder)-1])}
以上就是如何理解大數(shù)據(jù)中二叉搜索樹的后序遍歷序列，小編相信有部分知識點可能是我們?nèi)粘９ぷ鲿姷交蛴玫降?。希望你能通過這篇文章學(xué)到更多知識。更多詳情敬請關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼