輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則返回 true ,否則返回 false 。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同。 數(shù)據(jù)范圍： 節(jié)點(diǎn)數(shù)量 ，節(jié)點(diǎn)上的值滿足 ，保證節(jié)點(diǎn)上的值各不相同 要求：空間復(fù)雜度 ，時間時間復(fù)雜度 提示： 1.二叉搜索樹是指父親節(jié)點(diǎn)大于左子樹中的全部節(jié)點(diǎn)，但是小于右子樹中的全部節(jié)點(diǎn)的樹。 2.該題我們約定空樹不是二叉搜索樹 3.后序遍歷是指按照 “左子樹-右子樹-根節(jié)點(diǎn)” 的順序遍歷 4.參考下面的二叉搜索樹，示例 1
示例2
說明
不屬于上圖的后序遍歷，從另外的二叉搜索樹也不能后序遍歷出該序列 ，因為最后的2一定是根節(jié)點(diǎn)，前面一定是孩子節(jié)點(diǎn)，可能是左孩子，右孩子，根節(jié)點(diǎn)，也可能是全左孩子，根節(jié)點(diǎn)，也可能是全右孩子，根節(jié)點(diǎn)，但是[3,1,2]的組合都不能滿足這些情況，故返回false
加載中...