树的题目通常可以用递归解决，递归过程的本质是栈，因而理论上递归也可以用循环加堆栈（或者队列）解决
关于递归
递归非常容易让人思路混乱，看到网上有一种思路觉得很有用，就是假设子问题已经完美处理，你只需思考最终问题的处理思路，子问题的处理思路和最终问题的处理思路一样，这样思路就会清晰很多。
以下代码示例均为python版本
题目一：从上往下打印二叉树
题目描述：
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
算法思路：
很明显用层次遍历就可以解决，即广度遍历，从上往下打印，即每一层打印完之后需要按照父节点们的顺序继续打印子节点，
符合队列先进先出的特点，因而需要借助队列+循环判断就可以解决。
即借助队列，将根结点加入队列，每遍历到一个结点，将该结点移除出队列并将该结点的左右节点加入队列，重复这个过程，直至队列为空。
来源:剑指offer
关键字：队列 循环
代码如下
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
if root is None:
return []
tempnode = []
tempnode.append(root)
valres = []
while (len(tempnode) > 0):
node = tempnode.pop(0)
valres.append(node.val)
if node.left is not None:
tempnode.append(node.left)
if node.right is not None:
tempnode.append(node.right)
return valres
题目二：二叉树的镜像
题目描述：
操作给定的二叉树，将其变换为源二叉树的镜像。
如下图：
来源：剑指offer
算法思路：
从题目可以知道二叉树的镜像其实可以看成是左右子结点交换的过程，如下图：
来源：剑指offer
因而我们在前序遍历（顺序为根子树->左子树->右子树）的基础上，交换当前结点的左右子结点，就可以完成二叉树的镜像。
代码如下
# -*- coding:utf-8 -*-
'''
树的镜像
思路：递归交换左右结点
'''
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
if root is None:
return root
if root.left is None and root.right is None:
return root
tempNode = root.left
root.left = root.right
root.right = tempNode
self.Mirror(root.left)
self.Mirror(root.right)
关键字：递归 前序遍历
题目三：二叉搜索树的后序遍历序列
题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回True，否则返回False。假设输入的数组的任意两个数字都互不相同。
算法思路：
二叉搜索树：
是指一棵空树或者具有下列性质的二叉树：
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的结点。
来源：剑指offer
后序遍历顺序：左子树->右子树->根结点
1）递归方法
由后序遍历顺序可知，序列的最后一个元素为根结点，根据二叉搜索树的特点可知，左子树的每个非空结点都不大于根结点，右子树的每个非空结点都不小于根结点，题目中规定序列中各个结点都不重复，因此可以确定题目中给的测试用例中，左子树的每个结点势必都小于根结点，右子树的每个结点势必都大于根结点。
因此从左往右查找，找到第1个大于根结点的值则说明这个元素往左边的元素是左子树，该元素及往右边的元素到最后一个结点前为右子树。
如果左子树有任一元素大于根结点，或者右子树有任一元素小于根结点，说明该序列不为二叉搜索树遍历序列。
以此方法进行递归判断。
图片
图中最后一个元素8为根结点，元素9为从左往右序列中第一个大于根结点的值，以9往左为左子树，9和9往右到最后一个元素8前为右子树。
观察可知 如果符合二叉搜索树，则右子树序列元素都比根结点大
左右子序列以此方法递归可判断。
代码如下
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if sequence is None or len(sequence) == 0:
return False
return self.VerifyBST(sequence)
def VerifyBST(self,verifys):
if len(verifys) <= 1: # 只剩根结点
return True
root = verifys[-1]
temps = verifys[:-1]
lefts = []
rights = []
for i in range(len(temps)):
if temps[i] > root:
lefts = temps[0:i]
if i <= len(temps) - 1:
rights = temps[i:-1]
break
else:
lefts = temps
for v in rights:
if v < root:
return False
return self.VerifyBST(lefts) and self.VerifyBST(rights)
2）非递归方法（牛客网上看到的）
大致思路是根据后序遍历，将当前结点A作为根结点，遍历结点A前面序列的值，如果当前序列元素值小于结点A的值，并且前一序列元素值也大于结点A的值 说明不是二叉搜索树。
参考链接 牛客网
截图(侵删)：
图片侵删
关键字：递归 二叉搜索树特点
题目四：二叉树中和为某一值的路径
题目描述：
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
算法思路：
路径指的是树的根结点到叶结点所经过的结点，因此题目其实是求从根结点到某一叶结点的路径上所有结点的和是否为题目中要求的值。
因为计算是从根结点开始，所以其实可以看成是树的前序遍历的基础上计算路径和，由于题目要求打印出路径，因而每次遍历结点需要记录下当前结点，到达叶结点时需要判断该路径是否符合条件，当递归回退到上一个结点时需要从路径中移除当前结点即路径的最后一个结点，记录路径可以用堆栈。
示例：
来源：剑指offer
根结点到叶结点加入堆栈 ，堆栈中加入序列为 10，5， 4；
10+5+4不等于22，不记录路径；
弹出4，回到父结点5，堆栈序列 10,5；
右叶结点7 进栈 ，堆栈序列 10,5,7,等于22 ，记录路径；
弹出7，回到5；
弹出5，回到10；
叶结点12进栈，堆栈序列 10,12 等于 22 ，记录路径；
所以符合条件的路径为[10,5,7]和[10,12]。
# -*- coding:utf-8 -*-
"""
二叉树中和为某一值的路径
"""
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
return self.RealFindPath(root, 0, expectNumber, [], [])
def RealFindPath(self, root, sum, expectNumber, path, allpath):
if root is None:
return allpath
sum += root.val
path.append(root.val)
if root.left is None and root.right is None:
if sum == expectNumber:
allpath.append(path[:])
if root.left:
self.RealFindPath(root.left, sum, expectNumber, path, allpath)
if root.right:
self.RealFindPath(root.right, sum, expectNumber, path, allpath)
# 回退到上个结点前弹出当前元素
if len(path) > 0:
num = path.pop() # 弹出末尾元素
sum = sum - num
return allpath
关键字：递归 堆栈
题目五：对称的二叉树
题目描述：
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
算法思路：
递归方法：
如下图，由对称的二叉树观察得知，同一父节点的左子结点（6）的左结点（矩形1）和右子结点（6）的右结点（矩形1）如果不相等（一个为空另一个不为空也是不相等），或者同一父节点的左子结点（6）的右结点（圆形3）和右子结点（6）的左结点（圆形3）如果不相等（一个为空另一个不为空也是不相等），则说明该二叉树不为对称二叉树。
示例
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isSymmetrical(self, pRoot):
if pRoot is None:
return True
return self.IsRealSymmetrical(pRoot.left, pRoot.right)
def IsRealSymmetrical(self, Lroot, Rroot):
if (Lroot and Rroot is None) or (Rroot and Lroot is None):
return False
if Lroot is None and Rroot is None:
return True
if Lroot.val != Rroot.val:
return False
return self.IsRealSymmetrical(Lroot.left, Rroot.right) and self.IsRealSymmetrical(Lroot.right, Rroot.left)
关键字：递归 非递归
题目六：重建二叉树
题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
算法思路：
由前序序列和中序序列可得二叉树。由前序遍历的遍历过程可以知道，前序序列的第1个元素为根结点，在中序序列中找到根结点，序列中根结点往左为左子树，根结点往右为右子树。根据此方法递归可重建二叉树，递归的本质是栈（先进后出），因而最后递归返回的结点即为根结点。
来源：剑指offfer
关键字：递归
==============================
发现一个好玩的项目 ~
https://github.com/Wscats/piano
网友评论