二叉树感觉是所有数据结构中我掌握的最不好的一种，希望好好的刷两遍leetcode后可以掌握得好一些。
2018.10.22
104、二叉树的最大深度
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
else:
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
226、反转二叉树
class Solution(object):
def invertTree(self, root):
if not root:
return None
root.left, root.right = root.right, root.left
if root.left:
self.invertTree(root.left)
if root.right:
self.invertTree(root.right)
return root
617、合并二叉树
class Solution(object):
def mergeTrees(self, t1, t2):
"""
:type t1: TreeNode
:type t2: TreeNode
:rtype: TreeNode
"""
if t1 and t2:
t1.left = self.mergeTrees(t1.left, t2.left)
t1.right = self.mergeTrees(t1.right, t2.right)
t1.val += t2.val
return t1
else:
return t1 if t1 else t2
669、修剪二叉搜索树
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
if root.val > R:
return self.trimBST(root.left, L, R)
elif root.val < L:
return self.trimBST(root.right, L, R)
else:
root.left = self.trimBST(root.left, L, R)
root.right = self.trimBST(root.right, L, R)
return root
2018.10.23
107、二叉树的层次遍历Ⅱ
class Solution:
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
queue = [[root]]
rst = [[root.val]]
while queue:
cur = queue.pop(0)
temp = []
for i in cur:
if i.left:
temp.append(i.left)
if i.right:
temp.append(i.right)
if len(temp) >= 1:
queue.append(temp)
rst.append([x.val for x in temp])
return rst[::-1]
637、二叉树的层平均值
class Solution:
def averageOfLevels(self, root):
"""
:type root: TreeNode
:rtype: List[float]
"""
if not root:
return None
queue = [[root]]
rst = [root.val]
while queue:
cur = queue.pop(0)
temp = []
for i in cur:
if i.left:
temp.append(i.left)
if i.right:
temp.append(i.right)
if len(temp) >= 1:
queue.append(temp)
rst.append(sum([x.val for x in temp])/len(temp))
return rst
257、二叉树的所有路径
class Solution:
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return []
queue = [[root]]
rst = []
while queue:
i = queue.pop(0)
left = i[:]
right = i[:]
if not i[-1].left and not i[-1].right:
rst.append('->'.join([str(x.val) for x in i]))
if i[-1].left:
left.append(i[-1].left)
queue.append(left)
if i[-1].right:
right.append(i[-1].right)
queue.append(right)
return rst
235、二叉搜索树的最近公共祖先
这题没什么思路，参考了别人的答案。二叉搜索树满足p.val < r.val <q.val。而最近的祖先可能包括自己，所以应该满足p.val <= r.val <=q.val。然后进行递归查找
class Solution:
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if not root:
return None
minn = min(p.val, q.val)
maxn = max(p.val, q.val)
if minn <= root.val <= maxn:
return root
elif minn > root.val:
return self.lowestCommonAncestor(root.right, p, q)
elif maxn <= root.val:
return self.lowestCommonAncestor(root.left, p, q)
538、把二叉搜索树转换成累加树
二叉搜索树的中序遍历结果是一个递增的有序数列，那么把中序结果翻转就是递减的有序数列，只需要按照右中左的顺序遍历就可以了。
class Solution:
def __init__(self):
self.temp = 0
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
def reversemidtravel(root):
if not root:
return None
reversemidtravel(root.right)
root.val += self.temp
self.temp = root.val
reversemidtravel(root.left)
reversemidtravel(root)
return root
606、根据二叉树创建字符串
class Solution:
def __init__(self):
self.rst = []
def tree2str(self, t):
"""
:type t: TreeNode
:rtype: str
"""
if not t:
return ''
self.rst.append(str(t.val))
if t.left or t.right:
if t.left:
self.rst.append('(')
self.tree2str(t.left)
self.rst.append(')')
else:
self.rst.append('()')
if t.right:
self.rst.append('(')
self.tree2str(t.right)
self.rst.append(')')
return ''.join(self.rst)
110、平衡二叉树
class Solution:
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
if not root:
return True
if abs(max_depth(root.left) - max_depth(root.right)) > 1:
return False
return self.isBalanced(root.left) and self.isBalanced(root.right)
563、二叉树的坡度
调试了很久才AC的代码，自己都觉得写的烂，写完后看了一下别人的代码。
class Solution:
def findTilt(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.rst = 0
def getleftcounts(root):
count = 0
if not root.left:
return 0
queue = [root.left]
while queue:
temp = queue.pop(0)
count += temp.val
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
return count
def getrightcounts(root):
count = 0
if not root.right:
return 0
queue = [root.right]
while queue:
temp = queue.pop(0)
count += temp.val
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
return count
if not root or (not root.left and not root.right):
return 0
else:
if root.right and root.left:
self.rst += abs(getleftcounts(root) - getrightcounts(root))
self.rst += self.findTilt(root.right)
self.rst += self.findTilt(root.left)
elif root.left and not root.right:
self.rst += abs(getleftcounts(root) - getrightcounts(root))
self.rst += self.findTilt(root.left)
elif root.right and not root.left:
self.rst += abs(getleftcounts(root) - getrightcounts(root))
self.rst += self.findTilt(root.right)
return self.rst
别人的代码:
class Solution:
def findTilt(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def sumandtile(root):
if not root:
return 0, 0
leftsum, lefttile = sumandtile(root.left)
rightsum, righttile = sumandtile(root.right)
return leftsum + rightsum + root.val, abs(leftsum-rightsum) + lefttile + righttile
sum_tree, sum_tail = sumandtile(root)
return sum_tail
2018.10.25
101、对称二叉树
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def issametree(p, q):
if not p and not q:
return True
elif p and q:
if p.val == q.val:
return issametree(p.left, q.left) and issametree(p.right, q.right)
else:
return False
else:
return False
def reversetree(root):
if not root:
return None
root.left, root.right = root.right, root.left
reversetree(root.left)
reversetree(root.right)
return root
if not root:
return True
temp = reversetree(root.right)
return issametree(root.left, temp)
我这里先把右子树翻转了一下再与左子树比较是否相同，其实可以不翻转。
class Solution:
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def mirrortree(p, q):
if not p and not q:
return True
elif p and q:
if p.val == q.val:
return mirrortree(p.left, q.right) and mirrortree(p.right, q.left)
else:
return False
else:
return False
if not root or (not root.left and not root.right):
return True
p = root.left
q = root.right
return mirrortree(p, q)
543、二叉树的直径
class Solution:
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def maxdepth(root):
if not root:
return 0
return 1 + max(maxdepth(root.right), maxdepth(root.left))
if not root:
return 0
return max(maxdepth(root.left)+maxdepth(root.right),self.diameterOfBinaryTree(root.left),self.diameterOfBinaryTree(root.right))
2018.10.27
501、二叉搜索树中的众数
最笨的方法直接遍历一遍，还以为可以用递归等方法直接做出来，但是看了别人的答案也是直接遍历。
class Solution:
def __init__(self):
self.dic = {}
def findMode(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
def midtravel(root):
if not root:
return None
self.dic[root.val] = self.dic.get(root.val, 0) + 1
midtravel(root.left)
midtravel(root.right)
if not root:
return []
midtravel(root)
temp = sorted(self.dic.items(), key=lambda x:x[1], reverse=True)
res = []
maxcount = temp[0][1]
for i in temp:
if i[1] == maxcount:
res.append(i[0])
else:
break
return res
111、二叉树的最小深度
这题开始我想的有点简单了，认为直接‘return 1+ min(self.minDepth(root.left), self.minDepth(root.right))’就可以了，但后来发现错了，修改了一下代码。
class Solution:
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
if not root.left and not root.right:
return 1
if not root.left:
return 1 + self.minDepth(root.right)
if not root.right:
return 1 + self.minDepth(root.left)
return 1+ min(self.minDepth(root.left), self.minDepth(root.right))
2018.10.28
654、最大二叉树
class Solution:
def constructMaximumBinaryTree(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
def getsplittree(nums, start, end):
if start >= end:
return None
maxnum = max(nums[start:end])
root = TreeNode(maxnum)
maxindex = nums.index(maxnum)
root.left = getsplittree(nums, start, maxindex)
root.right = getsplittree(nums, maxindex+1, end)
return root
return getsplittree(nums, 0, len(nums))
814、二叉树剪枝
class Solution:
def pruneTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
def find1(root):
if not root:
return False
elif root.val == 1:
return True
else:
return find1(root.left) or find1(root.right)
if not find1(root):
return None
if not find1(root.left) and not find1(root.right):
root.left = None
root.right = None
elif not find1(root.left):
root.left = None
self.pruneTree(root.right)
elif not find1(root.right):
root.right = None
self.pruneTree(root.left)
else:
self.pruneTree(root.right)
self.pruneTree(root.left)
return root
94、二叉树的中序遍历
class Solution:
def __init__(self):
self.rst = []
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
self.inorderTraversal(root.left)
self.rst.append(root.val)
self.inorderTraversal(root.right)
return self.rst
2018.10.29
230、二叉搜索树中第K小的元素
class Solution:
def __init__(self):
self.rst = []
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
def midtravel(root):
if not root:
return None
midtravel(root.left)
self.rst.append(root.val)
midtravel(root.right)
midtravel(root)
return self.rst[k-1]
递归版中序遍历没办法在排到第k个元素时停止，因此可以用迭代。
class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
stack, res = [], []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop(-1)
res.append(root.val)
if len(res) >= k:
return res[k-1]
root = root.right
109、有序链表转换二叉搜索树
class Solution:
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
cur = head
nums = []
while cur:
nums.append(cur.val)
cur = cur.next
def getsplit(nums, start, end):
if start >= end:
return None
root = TreeNode(nums[(start+end)//2])
root.left = getsplit(nums, start, (start+end)//2)
root.right = getsplit(nums, (start+end)//2+1, end)
return root
return getsplit(nums, 0, len(nums))
我先把链表转换成列表再用前面构造最大二叉树的方法做的，后来参考别人答案可以直接从链表就开始递归构造
class Solution:
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
def convert(head, end):
if head == end:
return None
if head.next == end:
return TreeNode(head.val)
fast = head
mid = head
while fast!=end and fast.next!=end:
fast = fast.next.next
mid = mid.next
root = TreeNode(mid.val)
root.left = convert(head, mid)
root.right = convert(mid.next, end)
return root
return convert(head, None)
2018.10.31
114、二叉树展开为链表
定义了一个找左子树最靠右结点的一个函数，该结点的右孩子为根结点的右孩子。
class Solution:
def flatten(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
def getleaf(root):
if not root:
return None
elif not root.left and not root.right:
return root
elif root.right:
return getleaf(root.right)
else:
return getleaf(root.left)
if not root:
return
if not root.left and not root.right:
return
elif not root.left:
self.flatten(root.right)
elif not root.right:
root.right = root.left
root.left = None
self.flatten(root.right)
else:
leaf = getleaf(root.left)
leaf.right = root.right
root.right = root.left
root.left = None
self.flatten(root.right)
先把二叉树的前序，中序，后序遍历的迭代方法写一下
最开始的时候不太会，就照着之前写过的二叉搜索树中第K小的元素这题的迭代方法把中序迭代写完后，发现其实前序只要改一小部分就可以了，其实跟递归很类似。但是后序遍历比较麻烦，参考了别人的代码
前序迭代：
def preordertravel(root):
res, stack = [], []
while True:
while root:
res.append(root)
stack.append(root)
root = root.left
if not stack:
break
root = stack.pop()
root = root.right
return [x.val for x in res]
中序迭代：
def inordertravel(root):
res, stack = [], []
while True:
while root:
stack.append(root)
root = root.left
if not stack:
break
root = stack.pop()
res.append(root)
root = root.right
return [x.val for x in res]
后序迭代：
def postordertravel(root):
res, stack = [], [root]
while stack:
root = stack.pop()
res.append(root)
if root.left:
stack.append(root.left)
if root.right:
stack.append(root.right)
return [x.val for x in res[::-1]]
2018.11.1
96、不同的二叉搜索树
自己没找到规律，参考了别人思路：https://blog.csdn.net/sunnyyoona/article/details/42177001
image.png
class Solution:
def __init__(self):
self.rst = [1, 1]
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
for i in range(2, n+1):
temp = 0
for j in range(i):
temp += self.rst[j]*self.rst[i-j-1]
self.rst.append(temp)
return self.rst[-1]
199、二叉树的右视图
中等难度的二叉树已经写的让我怀疑人生了。这道题又又又又又不会，想到的就是最笨的广度优先遍历。但肯定有其它方法
class Solution:
def __init__(self):
self.rst = []
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
self.rst = [[root]]
temp = [root]
while temp:
nextfloor = []
for i in temp:
if i.left:
nextfloor.append(i.left)
if i.right:
nextfloor.append(i.right)
temp = nextfloor
if nextfloor:
self.rst.append(nextfloor)
return [x[-1].val for x in self.rst]
看了下别人提交的答案，好像很多也是广度优先遍历。
102、二叉树的层次遍历
class Solution:
def __init__(self):
self.rst = []
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
self.rst = [[root.val]]
temp = [root]
while temp:
nextfloor = []
for i in temp:
if i.left:
nextfloor.append(i.left)
if i.right:
nextfloor.append(i.right)
temp = nextfloor
if nextfloor:
self.rst.append([x.val for x in nextfloor])
return self.rst
173、二叉搜索树迭代器
class BSTIterator(object):
def __init__(self, root):
"""
:type root: TreeNode
"""
self.stack = []
self.inOrder(root)
def inOrder(self, root):
if not root:
return
self.inOrder(root.right)
self.stack.append(root.val)
self.inOrder(root.left)
def hasNext(self):
"""
:rtype: bool
"""
return len(self.stack) > 0
def next(self):
"""
:rtype: int
"""
return self.stack.pop()
2018.11.2
655、输出二叉树
class Solution(object):
def __init__(self):
self.rst = []
def printTree(self, root):
"""
:type root: TreeNode
:rtype: List[List[str]]
"""
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
if not root:
return ['']
depth = max_depth(root)
length = 2**depth - 1
template = ['']*length
cur = template[:]
cur[(length//2)] = root
self.rst.append(cur)
i = 2
while i <= depth:
nextnodes = template[:]
for j in range(len(template)):
if cur[j] != '':
if cur[j].left:
nextnodes[j - 2**(depth - i)] = cur[j].left
if cur[j].right:
nextnodes[j + 2**(depth - i)] = cur[j].right
i += 1
self.rst.append(nextnodes)
cur = nextnodes
for i in range(len(self.rst)):
self.rst[i] = [x if x=='' else str(x.val) for x in self.rst[i]]
return self.rst
