AC代碼:
class Solution(object): def findMode(self, root): """ :type root: TreeNode :rtype: List[int] """ self.ans = [] self.max = 1 if root == None: return [] r = root self.tmp = root.val+1 self.num = 0 while r.left: r = r.left self.tmp = r.val+1 self.findnum(root) return self.ans def findnum(self, node): if node.left != None: self.findnum(node.left) if node.val == self.tmp: self.num += 1 else: self.num = 1 self.tmp = node.val if self.num > self.max: self.ans = [node.val] self.max = self.num elif self.num == self.max: if node.val not in self.ans: self.ans.append(node.val) if node.right != None: self.findnum(node.right)解題思路:為了不使用額外的存儲(chǔ)空間,需要按照遞增的順序遍歷BST,中序遍歷可滿足遍歷的順序遞增,增加三個(gè)變量,tmp,max及num,tmp記錄的是上次訪問的數(shù),num記錄的是連續(xù)相等數(shù),max記錄的是最大的num。將num與max比較,若相等且ans中沒有該node,則將node加入ans中。若num大于max,則將ans清零,且加入該node,max換為num。
新聞熱點(diǎn)
疑難解答
網(wǎng)友關(guān)注