LeetCode 226
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
难倒大神的反转二叉树问题，其实这道题并不难，用递归和遍历都可解决。
class Solution:
# 递归
def invertTree(self, root):
if not root:
return None
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
# DFS
def invertTree2(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
LeetCode 572
本题判断二叉树是否为另一个数的子树。一种方法是使用递归，采用先序遍历的方法，先判断根节点，再判断左子树和右子树。对于每个节点，使用sameTree方法判断是否为相同的树。
class Solution:
def isSubtree(self, s, t):
if not s:
return False
if self.sameTree(s, t):
return True
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
def sameTree(self, s, t):
if not s and not t:
return True
if not s or not t:
return False
return s.val == t.val and self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right)
另一种方法是将树形结构转化为字符串，变成判断字符串是否含子字符串的问题。要注意两点：空节点也要进行标识，每个节点的值转化后要添加一个标识符，例如下文的“#”，如果不这样做的话，例如转化后的两个字符串分别为(“23 4 None None 5 None None”)和(“3 4 None None 5 None None”)，后面的字符串会被判断为前面字符串的子字符串，然而实际的树结构并非如此，设置标识符可以避免这个问题。
class Solution:
def isSubtree(self, s, t):
return self.convert(t) in self.convert(s)
def convert(self, p):
return "#" + str(p.val) + " " + self.convert(p.left) + self.convert(p.right) if p else "None"
LeetCode 437
链接：Path Sum III
路径总和问题，使用DFS遍历。每次调用dfs方法，sum的值会减去当前节点的值，遍历中当节点的值等于最新的sum值时，意味者当前路径总和即为最初的sum值。使用先序遍历，先调用dfs方法计算根节点路径，再递归左子树和右子树，最终输出结果。
class Solution:
def pathSum(self, root, sum):
if not root:
return 0
return self.dfs(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)
def dfs(self, root, sum):
res = 0
if not root:
return res
if root.val == sum:
res += 1
res += self.dfs(root.left, sum - root.val)
res += self.dfs(root.right, sum - root.val)
return res
LeetCode 102
题目链接：Binary Tree Level Order Traversal
本题为二叉树的层次遍历。学数据结构时接触这个遍历比较少，现在来学习一下，使用BFS解决。函数中的level代表当前的层次，默认为1。res代表转化后的数组。如果level大于数组的长度，代表已经遍历到了下一层，数组将在新的项中添加内容。
class Solution:
def levelOrder(self, root):
res = []
self.bfs(root, 1, res)
return res
def bfs(self, root, level, res):
if not root:
return
if level > len(res):
res.append([root.val])
else:
res[level - 1].extend([root.val])
self.bfs(root.left, level + 1, res)
self.bfs(root.right, level + 1, res)
LeetCode 105
题目链接：Construct Binary Tree from Preorder and Inorder Traversal
本题为根据前序遍历和中序遍历构造二叉树。虽然以前做过一些练习，不过还没有认真考虑过代码的实现方式。首先，树的根结点为前序遍历的第一个节点，而这个节点在中序遍历也一定存在。节点左边就是左子树的中序遍历，右边是右子树的中序遍历。利用分治的思想，分解成为两个较小的问题，然后递归处理，还原左子树和右子树，最后和根节点组成完整的树。
class Solution:
def buildTree(self, preorder, inorder):
if not inorder:
return None
root = inorder.index(preorder.pop(0))
tree = TreeNode(inorder[root])
tree.left = self.buildTree(preorder, inorder[:root])
tree.right = self.buildTree(preorder, inorder[root+1:])
return tree