[Leetcode] [Tag 树] Python 刷题总结
leetcode 树标签的题集中在94-117之间，解法往往有递归和循环两种，前中后序遍历、树的生成、平衡二叉树要非常熟悉。
94. Binary Tree Inorder Traversal 二叉树的中序遍历(Medium)
Given a binary tree, return the inorder traversal of its nodes' values.
给定一个二叉树，返回中序遍历节点的值。
思路：中序遍历根左右，经典思想递归或者循环。
循环写法：
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
res = []
stack = []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
res.append(node.val)
node = node.right
return res
递归写法：
def inorderTraversal1(self, root):
res = []
self.helper(root, res)
return res
def helper(self, root, res):
if root:
self.helper(root.left, res)
res.append(root.val)
self.helper(root.right, res)
96. Unique Binary Search Trees(Medium)
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
给一个整数n，返回有多少种不同的二叉排序树数量。
思路：其实该题更多的属于DP，每次固定一个根节点，左边所有的子节点小于根节点，而右边所有的节点大于根节点，可以列出F(i,n) = G(i-1) * G(n-i)。其中discuss区有个答案写的真心好，链接:Java solution DP Solution in 6 lines with explanation.
def numTrees(self, n):
dp = [1] * (n+1)
for i in range(2, n+1):
dp[i] = 0
for j in range(1, i+1):
dp[i] += dp[j-1] * dp[i-j]
return dp[n]
95. Unique Binary Search Trees II(Medium)
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
给一个整数n，返回所有不同结构二叉排序树
思路：上一题的加强版，不仅给出个数还需要返回出来，思路基本一样固定一个根节点，递归出 G(i-1) *和G(n-i)
def helper(self, first, last):
if first > last:
return [None]
if first == last:
return [TreeNode(first)]
res = []
for i in range(first, last+1):
for left in self.helper(first, i-1):
for right in self.helper(i+1, last):
tree = TreeNode(i)
tree.left = left
tree.right = right
res.append(tree)
return res
def generateTrees(self, n):
if n == 0:
return []
return self.helper(1, n)
98. Validate Binary Search Tree(Medium)
Given a binary tree, determine if it is a valid binary search tree (BST).
给定一棵树，判断其是否为合法的二叉排序树
思路：ps（二叉排序树的题常常可以想到中序遍历）两种方法，1、简单，递归中序遍历求得返回数组，循环判断是否为升序。2、非递归中序遍历 3、很巧妙，每次判断是否左子树小于父节点，右子树大于父节点，每个节点都将有一个最大值和最小值的区间，还要保存上一层遍历下来的最小值和最大值的节点，防止父节点的父节点有大于或小于孙该节点的情况。
#方法一
def inordertraversal(self, root):
if root is None:
return
self.inordertraversal(root.left)
self.res.append(root.val)
self.inordertraversal(root.right)
def isValidBST(self, root):
if root is None:
return True
self.res = []
self.inordertraversal(root)
for i in range(1, len(self.res)):
if self.res[i] <= self.res[i-1]:
return False
return True
#方法二
def isValidBST(self, root):
stack = []
inorder = float("-inf")
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if root.val <= inorder:
return False
inorder = root.val
root = root.right
return True
#方法三
def isValidBST(self, root):
if root is None:
return True
return self.helper(root, None, None)
def helper(self, root, minNode, maxNode):
if root is None:
return True
if (minNode and root.val <= minNode.val) or (maxNode and root.val >= maxNode.val):
return False
return self.helper(root.left, minNode, root) and self.helper(root.right, root, maxNode)
99. Recover Binary Search Tree(hard)
Two elements of a binary search tree (BST) are swapped by mistake.Recover the tree without changing its structure.
2两个二叉排序树的节点被错误的交换了，请恢复这颗二叉排序树但不改变其结构
思路：依然是利用中序遍历BST的结构为升序排序，保存好前一次遍历的节点(prenode)
若第一次prenode>=root，则第一个错误节点firstnode为本次遍历节点
若第二次prenode>=root，则第二个错误节点senode为本次节点
def Inordertravesal(self, root):
if root is None:
return None
self.Inordertravesal(root.left)
if self.firstnode is None and self.prenode and self.prenode.val >= root.val:
self.firstnode = self.prenode
if self.firstnode and self.prenode and self.prenode.val >= root.val:
self.senode = root
self.prenode = root
self.Inordertravesal(root.right)
def recoverTree(self, root):
self.firstnode = None
self.senode = None
self.prenode = None
self.Inordertravesal(root)
if self.firstnode and self.senode:
self.firstnode.val, self.senode.val = self.senode.val, self.firstnode.val
100. Same Tree(easy)
Given two binary trees, write a function to check if they are the same or not.
给定两颗二叉排序树，判断是否相同。
思路：递归判断每一个节点，若都为空返回True，若一个为空一个非空或者节点值不相等返回False
def isSameTree(self, p, q):
if p is None and q is None:
return True
if p is None or q is None or p.val!=q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
101. Symmetric Tree(easy)
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
给定一颗二叉树，判断其是不是本身对称的（镜像）
思路：可以把100题当轮子用，把左右交换一下就ok了。
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
return self.isSameTree(root.left, root.right)
def isSameTree(self, p, q):
if p is None and q is None:
return True
if p is None or q is None or p.val != q.val:
return False
return self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)
102. Binary Tree Level Order Traversal(easy)
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
给定一棵树，返回层次遍历节点的值
思路：层次遍历基本思路，借助队列（栈）
def levelOrder(self, root):
if root is None:
return []
queue, res = [root],[]
while queue:
tmp_res, queue0 = [],[]
for i in queue:
tmp_res.append(i.val)
if i.left:
queue0.append(i.left)
if i.right:
queue0.append(i.right)
res.append(tmp_res)
queue = queue0
return res
103. Binary Tree Zigzag Level Order Traversal(Medium)
之字型打印
思路：102题的变形，利用队列，再对奇数层进行反转就行。
def zigzagLevelOrder(self, root):
if root is None:
return []
queue = [root]
res = []
while queue:
tmpNode = []
queue0 = [i for i in queue]
queue = []
for tree in queue0:
tmpNode.append(tree.val)
if tree.left:
queue.append(tree.left)
if tree.right:
queue.append(tree.right)
res.append(tmpNode)
for i in range(0, len(res)):
if i % 2:
res[i].reverse()
return res
104. Maximum Depth of Binary Tree(Easy)
二叉树的深度
思路：递归没深入一层取最大+1，非常地简洁，很多题可以当轮子用。
def maxDepth(self, root):
if root is None:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
105. Construct Binary Tree from Preorder and Inorder Traversal(Medium)
根据中序遍历和前序遍历重组二叉树
思路：学过数据结构应该知道中序+前序 or中序+后续可以确定一棵二叉树，关键在于中序的根节点可以严格把左右两边的子树分割开，而前序或者后续可以确定根节点的位置，递归解决方法如下：
def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return None
index = inorder.index(preorder.pop(0)) #找到根节点在中序中的位置
root = TreeNode(inorder[index])
root.left = self.buildTree(preorder[:index], inorder[:index])
root.right = self.buildTree(preorder[index:], inorder[index+1:])
return root
106. Construct Binary Tree from Inorder and Postorder Traversal(Medium)
根据中序遍历和后序遍历重组二叉树。与105同理
def buildTree(self, inorder, postorder):
if not postorder:
return None
value = postorder.pop()
ind = inorder.index(value)
root = TreeNode(value)
root.left = self.buildTree(inorder[:ind],postorder[:ind])
root.right = self.buildTree(inorder[1+ind:],postorder[ind:])
return root
108. Convert Sorted Array to Binary Search Treel(Easy)
转换排序好的数组为平衡二叉树。
思路：非常经典的生成二叉树的方法，平衡二叉树要求子树高度差为1，所以每次找到最中间的数值，进行递归即可。
def sortedArrayToBST(self, nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
109. Convert Sorted List to Binary Search Tree(Medium)
思路：108题的升级版，关键在于对链表进行二分，用pre来保存，细节要到位。
def sortedListToBST(self, head):
if head is None:
return None
if head.next is None:
return TreeNode(head.val)
pre = None
slow = fast = head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
root = TreeNode(slow.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(slow.next)
return root
110. Balanced Binary Tree(Easy)
思路：递归实现，这道题注意一下递归返回值就好了
def dfs(self, root):
if root is None:
return 0
left = self.dfs(root.left)
right = self.dfs(root.right)
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
return max(left, right) + 1
def isBalanced(self, root):
return self.dfs(root) != -1
111. Minimum Depth of Binary Tree(Easy)
思路：最小树的深度，要考虑到如果树一边有孩子一边没有，那么取max，否则取min.
递归的写法：
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
if root.left is not None and root.right is not None:
return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
else:
return max(self.minDepth(root.left), self.minDepth(root.right)) + 1
遇到最小深度的题也很适合BFS：
def minDepth(self, root):
if root is None:
return 0
stack, depth = [root], 0
while stack:
depth += 1
tmp = []
for p in stack:
if p.left is None and p.right is None:
return depth
if p.left:
tmp.append(p.left)
if p.right:
tmp.append(p.right)
stack = tmp
return depth
112. Path Sum(Easy)
思路：路径和，每递归一次减去root.val即可。
def hasPathSum(self, root, sum):
if root is None:
return False
sum -= root.val
if root.left is None and root.right is None and sum == 0:
return True
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
113. Path Sum II(Medium)
思路：与112类似，深度优先的递归方法。
def pathSum(self, root, sum):
if not root:
return []
res = []
self.helper(root, sum, res, [])
return res
def helper(self, root, sum, res, tmp):
if sum == root.val and root.left is None and root.right is None:
tmp.append(root.val)
res.append(tmp)
else:
if root.left:
self.helper(root.left, sum - root.val, res, tmp + [root.val])
if root.right:
self.helper(root.right, sum - root.val, res, tmp + [root.val])
114. Flatten Binary Tree to Linked List(Medium)
思路：该题就是一个树转换成前序遍历的单链表，先通过dfs遍历到最后一个节点，每次保存最后一个节点pre(设为全局变量)，再回溯当前节点右孩子指向pre。
def flatten(self, root):
self.pre = None
self.dfs(root)
def dfs(self, root):
if not root:
return None
self.dfs(root.right)
self.dfs(root.left)
root.right = self.pre
root.left = None
self.pre = root
116. Populating Next Right Pointers in Each Node(Medium)
思路: 该题为满二叉树(prefect)，层次遍历的方法比较容易想到，递归的话分两种情况，首先是root存在左右两孩子的时候，需要root.left.next = root.right如案例2->3,4->5，其次是root.next存在那么root.right.next = root.next.left 如案例5->6。
递归解法：
def connect(self, root):
if not root or not root.left:
return
root.left.next = root.right
if root.next:
root.right.next = root.next.left
self.connect(root.left)
self.connect(root.right)
BFS解法：
def connect(self, root):
if root is None:
return
queue = [root]
while queue:
tmpqueue = []
for i,q in enumerate(queue):
if i<len(queue)-1:
q.next = queue[i+1]
else:
q.next = None
if q.left:
tmpqueue.append(q.left)
if q.right:
tmpqueue.append(q.right)
queue = tmpqueue
117. Populating Next Right Pointers in Each Node II(Medium)
思路:该题与116区别在于树的种类没有限制,递归比较复杂用BFS循环的比较方便。
def connect(self, root):
if not root:
return None
queue = [root]
while queue:
tmp = []
while queue:
node = queue.pop(0)
if queue:
node.next = queue[0]
else:
node.next = None
if node.left:
tmp.append(node.left)
if node.right:
tmp.append(node.right)
queue = tmp
145. Binary Tree Postorder Traversal(hard)
后续遍历题：先按根右左的顺序遍历树，然后取逆序即可。
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
res.append(node.val)
return res[::-1]
