Leetcode 算法题15

669. Trim a Binary Search Tree

给定一个范围，对二叉搜索树进行修剪

Example 1:

Input: 
    1
   / \
  0   2

  L = 1
  R = 2

Output: 
    1
      \
       2

Example 2:

Input: 
    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

Output: 
      3
     / 
   2   
  /
 1

我的代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def trimBST(self, root, L, R):
        """
        :type root: TreeNode
        :type L: int
        :type R: int
        :rtype: TreeNode
        """
        if not root:
            return None
        elif root.val > R:
            return self.trimBST(root.left,L,R)
        elif root.val < L:
            return self.trimBST(root.right,L,R)
        root.left = self.trimBST(root.left,L,R)
        root.right = self.trimBST(root.right,L,R)
        return root

747. Largest Number Greater Than Twice of Others

给定一个列表，如果其中最大的数都大于其他数的两倍，输出这个数的索引，否则输出-1

Example 1:

Input: nums = [3, 6, 1, 0]
Output: 1
Explanation: 6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x.  The index of value 6 is 1, so we return 1.

Example 2:

Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn't at least as big as twice the value of 3, so we return -1.

我的代码：

class Solution(object):
    def dominantIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = nums.index(max(nums))
        maxnum = max(nums)
        nums.pop(ans)
        return ans if max(nums) <= (maxnum / 2) else -1

另外一个版本感觉计算量小一点：

class Solution(object):
    def dominantIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_ ,next_= max(nums[0],nums[1]),min(nums[0],nums[1])
        index_ = nums.index(max_)
        for i in range(len(nums)):
            if nums[i] > max_:
                max_,next_,index_ = nums[i],max_,i
            elif nums[i] > next_:
                next_ = nums[i]
        return index_ if max_/2 >= next_ else -1

637. Average of Levels in Binary Tree

计算二叉树每层的平均值

Example 1:

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

我的代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        list_ = [root]
        ans = []
        while list_:
            sum_ = 0
            next_ = []
            for i in list_:
                sum_ += i.val
                if i.left:
                    next_.append(i.left)
                if i.right:
                    next_.append(i.right)
            ans.append(round(sum_)/round(len(list_),5))
            list_ = next_
        return ans     

大神的代码：

def averageOfLevels(self, root):
    info = []
    def dfs(node, depth = 0):
        if node:
            if len(info) <= depth:
                info.append([0, 0])
            info[depth][0] += node.val
            info[depth][1] += 1
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
    dfs(root)

    return [s/float(c) for s, c in info]

104. Maximum Depth of Binary Tree

求二叉树的最大深度

我的代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        list_ = [root]
        depth = 0
        while list_:
            depth += 1
            next_ = []
            for i in list_:
                if i.left:
                    next_.append(i.left) 
                if i.right:
                    next_.append(i.right)
            list_ = next_
        return depth
            

大神的代码：一行超人~

def maxDepth(self, root):
    return 1 + max(map(self.maxDepth, (root.left, root.right))) if root else 0

226. Invert Binary Tree

翻转二叉树

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

我的代码：关于这种树的用列表进行堆栈出栈比较简单

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        list_ = [root]
        while list_:
            next_ = []
            for i in list_:
                i.left,i.right = i.right,i.left
                if i.left:
                    next_.append(i.left)
                if i.right:
                    next_.append(i.right)
            list_ = next_
        return root
            

大神的代码：三种方法

# recursively
def invertTree1(self, root):
    if root:
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root
        
# BFS
def invertTree2(self, root):
    queue = collections.deque([(root)])
    while queue:
        node = queue.popleft()
        if node:
            node.left, node.right = node.right, node.left
            queue.append(node.left)
            queue.append(node.right)
    return root
    
# DFS
def invertTree(self, root):
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            node.left, node.right = node.right, node.left
            stack.extend([node.right, node.left])
    return root