二叉树专题系列
1. 镜像类
题目描述：
操作给定的二叉树，将其变换为源二叉树的镜像。
Ying的解法：
二叉树的组成是根节点和左右指针，因此解决二叉树问题，一般要先讨论根节点的是否为空，决定了树的存在性，往往也是需要作为一种特殊情况需要单独拿出来考虑；然后再对普通情况进行把握。
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
root1 = root
if root is None:
return root
else:
root.left,root.right = root.right,root.left
if root.left is not None:
self.Mirror(root.left)
if root.right is not None:
self.Mirror(root.right)
return root1
题目描述：
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
Ying的解法：
这道题和上道题看上去没有什么本质区别，对称二叉树和它的镜像二叉树是相同的，所以我一开始的想法是构建该树的镜像二叉树，然后通过任意一种遍历方式比较两棵树是否相同，但是具体操作发现，对于完全二叉树没有问题，但是无法通过所有的样例。即使同时考虑通过两种遍历方式（先序中序或者中序后序），也无法通过所有样例。考虑每个节点的值相同的情况。
因此，考虑换一种解题方法，运用递归的思想，发现，判断是否对称，一个二叉树需要满足左右子树关于中心线左右互换，即根节点的左孩子等于右孩子，左孩子的左孩子等于右孩子的右孩子，左孩子的右孩子等于右孩子的左孩子......
由此，得到如下代码：
class Solution:
def isSame(self,left,right):
#取非不能用!，而是not
if not left or not right:
if not left and not right:
return True
return False
if left.val != right.val:
return False
r1 = self.isSame(left.left,right.right)
r2 = self.isSame(left.right,right.left)
if r1 and r2:
return True
def isSymmetrical(self, pRoot):
# write code here
if not pRoot:
return True
return self.isSame(pRoot.left,pRoot.right)
2. 层次遍历类
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
Ying的解法：
这道题很简单，很基本的二叉树层次遍历问题。注意这道题要求的是打印节点，所以在提交函数中不需要写return（写也不错），而应该是print；此外，在遍历当前节点时，需要将其左右节点存储在一个队列中，队列的实现，python有天然的优势，通过列表结构的pop(0)方法实现，转化为只要列表不空，就打印列表元素的问题，以下是代码实现。
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if root==None:
return None
tempQue = []
node = root
tempQue.append(node)
while tempQue:
node = tempQue.pop(0)
print(node.val)
if node.left:
tempQue.append(node.left)
if node.right:
tempQue.append(node.right)
题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
Ying的解法：
与上一题相比，本题的题目要求仅多了一个每一层输出一行，我最开始的想法是每输出一层打印一个换行，但是题目要求是输出，要求返回二维数组，而不是打印。每一行相当于二维数组中的一维数组元素，同样的问题，如何区分一层结束？首先开辟一个空的二维数组和两个一维数组，一个存节点，一个存值，考虑加入标记'#'表示一行输出完毕，当遇到'#'时，一维节点数组弹出'#'的同时，将值列表添加到二位列表中，再清空，同时节点列表插入'#'；区分当遇到最后一个'#'时，停止操作，返回二维列表。实现代码如下：
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if not pRoot:
return []
tempQue = []
# 存放二维数组中的每个list元素
vaList = []
# 存放最后结果的二维数组
resultList = []
node = pRoot
tempQue.append(node)
tempQue.append('#')
while tempQue:
if tempQue[0]!='#':
node = tempQue.pop(0)
vaList.append(node.val)
if node.left:
tempQue.append(node.left)
if node.right:
tempQue.append(node.right)
elif tempQue[0]=='#' and len(tempQue)!=1:
tempQue.pop(0)
resultList.append(vaList)
vaList = []
tempQue.append('#')
elif tempQue[0]=='#' and len(tempQue)==1:
tempQue.pop(0)
resultList.append(vaList)
return resultList
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
Ying的解法：
这道题在上个题目的基础上要求奇数层从左到右打印，偶数行从右到左打印,我的第一想法是在上一题的代码基础上，用栈实现，想要寻求不同行之间一致的操作规律，结果把自己绕晕了。以下这种做法比较巧妙，通过维护两个列表，分别存储相邻两层之间的节点，当前节点的左孩子右孩子添加到另一个列表中，不停出栈，直到当前列表为空，再遍历另一个列表重复之前操作，只不过之前是先左后右，这次是先右后左。在此遍历过程中，两个列表始终有一个不空，直到都为空，返回二位列表。
class Solution:
def Print(self, pRoot):
# write code here
if not pRoot:
return []
#两个列表存放节点元素
list1 = []
list2 = []
# 存放二维数组中的每个list元素，节点的值
vaList = []
# 存放最后结果的二维数组
resultList = []
node = pRoot
list1.append(node)
while list1 or list2:
while list1:
node = list1.pop()
vaList.append(node.val)
if node.left:
list2.append(node.left)
if node.right:
list2.append(node.right)
if not list1:
resultList.append(vaList)
vaList = []
while list2:
node = list2.pop()
vaList.append(node.val)
if node.right:
list1.append(node.right)
if node.left:
list1.append(node.left)
if not list2:
resultList.append(vaList)
vaList = []
return resultList
3. 深度问题类
题目描述：二叉树中和为某一值的路径
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
Ying的思路：
因为要输出的是一个二维列表，而且列表中元素的长度要逆序输出。即对于所有和为给定值的路径，先返回深度大的路径。这个代码自己没有写出来，是借鉴书上和他人做法的。比较巧妙的是对于不同的路径，始终维持的是一个一维列表，当还能继续搜索时（左右子节点不全为空），则继续搜索，但搜索完之后要返回上一步，寻找其他满足情况的路径。二叉树的问题，经常通过列举，把题意理解清楚之后，举例子走一遍，很有帮助。以下是代码：
import copy
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def getSum(self, array):
sum = 0
for i in array:
sum += i
return sum
def Find(self, root, expectNumber, onePath, pathArray):
if not root:
return pathArray
onePath.append(root.val)
if self.getSum(onePath) == expectNumber and not root.left and not root.right:
pathArray.append(copy.deepcopy(onePath))
elif self.getSum(onePath) != expectNumber:
if root.left:
self.Find(root.left, expectNumber, onePath, pathArray)
onePath.pop(-1)
if root.right:
self.Find(root.right, expectNumber, onePath, pathArray)
onePath.pop(-1)
# 感觉这样写有问题，如果已经到叶子节点,该路径值不满足怎么办
# 其实是没有问题的，不满足条件的路径不做任何操作就可以了
# 二维列表中的列表是动态更新的，维护的是一个，而不是每个以为列表都需要重新开辟，所以这里用的是深拷贝
def FindPath(self, root, expectNumber):
onePath = []
pathArray = []
self.Find(root, expectNumber, onePath, pathArray)
return pathArray
题目描述:二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
Ying的思路：
二叉树的深度是由它从根节点开始到叶子节点的所有路径中最长的一条决定的。叶子节点的深度为1，空树的深度是0，其他二叉树的深度游它左右子树长度的最大值决定。左右子树分别有各自的左右子树，它的深度同样等于它的左右子树深度的最大值。以此递归下去，就可以求得二叉树的深度。代码如下所示：
class Solution:
def TreeDepth(self, pRoot):
# write code here
if pRoot is None:
return 0
else:
return max(self.TreeDepth(pRoot.left),self.TreeDepth(pRoot.right)) + 1
题目描述：平衡二叉树
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
Ying的思路：
平衡二叉树是指左右子树深度相差不超过1的二叉树。因此，直接的想法便是得到做右子树的深度，判断差的绝对值是否不大于1。接下来，就是如何计算左右子树的深度。这里需要列举几种情况进行讨论当左右子节点都存在时，和上个题一样，比较左右子树最大深度加1即可，但是若左子树或右子树不存在，那么比较过程的递归函数中node.left和node.right是不存在的，会报错，因此，这两种情况要分开逃理论一下，至此，得到如下代码：
class Solution:
def getHight(self,node):
if not node.left and not node.right:
return 0
if node.left or node.right:
if node.left and node.right:
return max(self.getHight(node.left),self.getHight(node.right))+1
if node.left:
return self.getHight(node.left)+1
if node.right:
return self.getHight(node.right)+1
def IsBalanced_Solution(self, pRoot):
# write code here
if not pRoot:
return True
hLeft = 0
hRight = 0
if pRoot.left or pRoot.right:
if pRoot.left:
hLeft = self.getHight(pRoot.left)
if pRoot.right:
hRight = self.getHight(pRoot.right)
if abs(hLeft-hRight)<=1:
return True
return False
==未完待续
作者原创，欢迎交流，如需转载请先联系作者。
