LeetCode 题目-501. 二叉搜索树中众数/538.把二叉搜索树转换为累加树I(python实现)

81 阅读 0 评论 54 点赞

我是靠谱客的博主动人小猫咪，这篇文章主要介绍LeetCode 题目-501. 二叉搜索树中众数/538.把二叉搜索树转换为累加树I(python实现)，现在分享给大家，希望可以做个参考。

作为要准备踏入码农行业的人来说，要准备校招，怎么能不去刷刷LeetCode呢？

501. 二叉搜索树中众数

题目要求

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树

例如

复制代码

1
2
3
4
5
6
7
8
9
10

给定 BST [1,null,2,2],
  1
    
     2
    /
   2
  返回[2]

提示：如果众数超过1个，不需考虑输出顺序

分析

方法:
搜索树的中序遍历是递增的序列，所以我们其实可以把问题转换成寻转一串数的众数

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution(object):
    def findMode(self, root):
        self.lists={}
        self.read(root)
        #将字典按照值排序
        res = sorted(self.lists.items(), key=lambda d: d[1],
        reverse=True)
        #字典推导式返回一个列表
        return [x[0] for x in res if x[1] == res[0][1]]

    def read(self,root):
        if root is None :
            return
        self.read(root.left)
        if root.val in self.lists:
            self.lists[root.val]= self.lists[root.val]+1
        else:
            self.lists[root.val]=1
        self.read(root.right)

538.把二叉搜索树转换为累加树

题目要求

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如

复制代码

1
2
3
4
5
6
7
8
9
10
11
12

输入: 二叉搜索树:
              5
            /   
           2     13

输出: 转换为累加树:
             18
            /   
          20     13

分析方法:
以右-根-左顺序遍历树，并进行值的累加

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        self.nums=0
        self.read_right(root)
        return root
    def read_right(self,root):
        if root is None:
            return
        self.read_right(root.right)
        root.val=root.val+self.nums
        self.nums=root.val
        self.read_right(root.left)