剑指offer（2）
23.从上往下打印二叉树
从上往下打印出二叉树的每个节点，同层节点从左至右打印。（依次打印出每层的结点值）
需要一个队列和一个存储数据的数组
# -*- 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):
# write code here
if not root:
return []
result = [] #存储结果
queue = [] #实现队列
queue.append(root)
while queue:
curNode = queue.pop(0)
result.append(curNode.val)
if curNode.left:
queue.append(curNode.left)
if curNode.right:
queue.append(curNode.right)
return result24.二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。（二叉搜索树的中序遍历是有序的）
根据后续遍历的性质，尾元素必定是树的根，同时小于尾元素的值是左子树，大于尾元素的值为右子树，且序列前半部分均小于尾元素，后半部分均大于尾元素（如果同时存在左右子树的话），可以将序列划分左子树序列和右子树序列，然后递归比较是否每一段均满足此性质。减少递归深度的办法：某段的元素个数如果<=3，则返回True；某整段的最小元素不小于尾元素或者整段的最大元素不大于尾元素，说明仅有左子树或者右子树，返回True。
整数序列的最后一个值是根结点，然后比根结点小的值是左子树，比根节点大的是右子树，递归左右子树
如序列： 1，3，2，5，6，7，4
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
length = len(sequence)
if length == 0:
return False
else:
root = sequence[-1] #原始数组中最后一个元素为根节点
left = 0
while sequence[left] < root: #找到最左边的元素索引 加1，因为 ：left是开区间
left += 1
right = left
while right < length-1:
if sequence[right] < root: #如果存在根节点都比右结点还大的数，则为False
return False
right += 1
if left == 0:
return True
else:
left_ret = self.VerifySquenceOfBST(sequence[:left])
if left == right:
return True
else:
right_ret = self.VerifySquenceOfBST(sequence[left: right])
return left_ret and right_ret25.二叉树中和为某一值的路径
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
输入一棵二叉树和一个值，求从根结点到叶结点的和等于该值的路径
#使用深度优先的方法
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
#使用深度优先方法
if not root:
return []
res, path, sums = [], [], [] #分别保存结果，结点路径， 每个结点路径和
path.append(root)
sums.append(root.val)
def dfs(root):# 深度优先遍历全部结点，
if root.left:
path.append(root.left)
sums.append(sums[-1] + root.left.val)
dfs(root.left)
if root.right:
path.append(root.right)
sums.append(sums[-1] + root.right.val)
dfs(root.right)
if not root.left and not root.right:
if sums[-1] == expectNumber:
res.append([p.val for p in path])
print([p.val for p in path])
print(sums)
path.pop() #去除做结点， 使其遍历 右结点
sums.pop()
dfs(root)
return res
# def FindPath(self, root, expectNumber):
# # write code here
# if not root:
# return []
# result = []
# def FindPathMain(root, path, currentSum):
# currentSum += root.val
# path.append(root)
# isLeaf = root.left == None and root.right == None
#
# if currentSum == expectNumber and isLeaf:
# onePath = []
# for node in path:
# onePath.append(node.val)
# result.append(onePath)
#
# if currentSum < expectNumber:
# if root.left:
# FindPathMain(root.left, path, currentSum)
# if root.right:
# FindPathMain(root.right, path, currentSum)
# path.pop()
#
# FindPathMain(root, [], 0)
# return result
pNode1 = TreeNode(10)
pNode2 = TreeNode(5)
pNode3 = TreeNode(12)
pNode4 = TreeNode(4)
pNode5 = TreeNode(7)
pNode1.left = pNode2
pNode1.right = pNode3
pNode2.left = pNode4
pNode2.right = pNode5
S = Solution()
print(S.FindPath(pNode1, 22))26.复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）