溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章給大家分享的是有關如何理解大數據中二叉搜索樹的后序遍歷序列，小編覺得挺實用的，因此分享給大家學習，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。
輸入一個整數數組，判斷該數組是不是某二叉搜索樹的后序遍歷結果。如果是則返回 true，否則返回 false。假設輸入的數組的任意兩個數字都互不相同。
參考以下這顆二叉搜索樹：
5
/ \
2 6
/ \
1 3示例 1：
輸入: [1,6,3,2,5]
輸出: false示例 2：
輸入: [1,3,2,6,5]
輸出: true提示：
數組長度 <= 1000
解題思路：
1，后續遍歷的特點［左子樹｜右子樹｜根］
2，所以最后一個元素一定是根節點
3，從左往后遍歷，找到第一個比根元素大的元素，從這個位置將數組拆成左右子數
4，判斷右邊子樹，如果有元素比根元素大，那么不符合二叉搜索樹的性質
5，遞歸遍歷，直到葉子節點
6，對于這類題目是兒叉樹和后續遍歷的一個結合，主要考核對二叉樹的理解
代碼實現：
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])}
以上就是如何理解大數據中二叉搜索樹的后序遍歷序列，小編相信有部分知識點可能是我們日常工作會見到或用到的。希望你能通過這篇文章學到更多知識。更多詳情敬請關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
