二叉樹感覺是所有數(shù)據(jù)結(jié)構(gòu)中我掌握的最不好的一種，希望好好的刷兩遍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、反轉(zhuǎn)二叉樹
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。而最近的祖先可能包括自己，所以應(yīng)該滿足p.val <= r.val <=q.val。然后進(jìn)行遞歸查找
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、把二叉搜索樹轉(zhuǎn)換成累加樹
二叉搜索樹的中序遍歷結(jié)果是一個遞增的有序數(shù)列，那么把中序結(jié)果翻轉(zhuǎn)就是遞減的有序數(shù)列，只需要按照右中左的順序遍歷就可以了。
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
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、二叉樹的坡度
調(diào)試了很久才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)
我這里先把右子樹翻轉(zhuǎn)了一下再與左子樹比較是否相同，其實(shí)可以不翻轉(zhuǎn)。
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、二叉搜索樹中的眾數(shù)
最笨的方法直接遍歷一遍，還以為可以用遞歸等方法直接做出來，但是看了別人的答案也是直接遍歷。
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、二叉樹的最小深度
這題開始我想的有點(diǎn)簡單了，認(rèn)為直接‘return 1+ min(self.minDepth(root.left), self.minDepth(root.right))’就可以了，但后來發(fā)現(xiàn)錯了，修改了一下代碼。
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
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))
我先把鏈表轉(zhuǎn)換成列表再用前面構(gòu)造最大二叉樹的方法做的，后來參考別人答案可以直接從鏈表就開始遞歸構(gòu)造
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、二叉樹展開為鏈表
定義了一個找左子樹最靠右結(jié)點(diǎn)的一個函數(shù)，該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)的右孩子。
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小的元素這題的迭代方法把中序迭代寫完后，發(fā)現(xiàn)其實(shí)前序只要改一小部分就可以了，其實(shí)跟遞歸很類似。但是后序遍歷比較麻煩，參考了別人的代碼
前序迭代：
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、不同的二叉搜索樹
自己沒找到規(guī)律，參考了別人思路：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、二叉樹的右視圖
中等難度的二叉樹已經(jīng)寫的讓我懷疑人生了。這道題又又又又又不會，想到的就是最笨的廣度優(yōu)先遍歷。但肯定有其它方法
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]
看了下別人提交的答案，好像很多也是廣度優(yōu)先遍歷。
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
