首先回顾树的知识：

1. 通过二叉树的先序遍历与中序遍历、或者后序遍历与中序遍历可以还原出唯一的二叉树，但是根据先序遍历与后序遍历无法还原出唯一的二叉树。

二叉树

首先一定要弄清楚二叉树的先序遍历、中序遍历、后序遍历与层次遍历！

• 先序遍历：root, left, right 排在第一的永远是根节点

• 中序遍历：left, root, right 永远知道最左的叶子节点与最右的叶子节点

• 后序遍历：left, right, root 排在最后的永远是根节点

先序遍历：
def PreOrder(root):
  if root is not None:
    VisitBinaryTreeNode(root)
    PreOrder(leftChild)
    PreOrder(rightChild)

def VisitBinaryTreeNode(node):
  # 如果node节点不是空节点
  if node.data is not '#':
    print(node.data)

中序遍历：
def InOrder(root):
  if root is not None:
    InOrder(leftChild)
    VisitBinaryTreeNode(root)
    InOrder(rightChild)

后序遍历：
def PostOrder(root):
  if root is not None:
    PostOrder(leftChild)
    PostOrder(rightChild)
    VisitBinaryTreeNode(root)

Q1: #105 Construct Binary Tree from Preorder and Inorder Traversal 给定二叉树的先序遍历与中序遍历，构建二叉树

问题描述：

例如：
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7] (层次遍历)

Input: preorder = [-1], inorder = [-1]
Output: [-1] (层次遍历)

解题思路： 先序遍历preorder的第一个元素肯定是整个树的根节点。那么在中序遍历inorder中找到根节点坐标，根节点之前的序列就是左子树，根节点之后的序列就是右子树。于是可以用递归的思想。把inorder从根节点位置分解成左子树与右子树两部分，同时preorder在根节点之后紧接的一串是左子树，再剩下的就是右子树。

整个问题：preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
分解为：
根：3
左子树：preorder = [9], inorder = [9]
右子树：preorder = [20,15,7], inorder = [15,20,7]

Q2: #106 Construct Binary Tree from Postorder and Inorder Traversal 给定二叉树的后序遍历与中序遍历，构建二叉树

解题思路： 和上面一题一样的思路。后序遍历postorder的最后一个元素肯定是整个树的根节点。那么在中序遍历inorder中找到根节点坐标，根节点之前的序列就是左子树，根节点之后的序列就是右子树。于是可以用递归的思想。把inorder从根节点位置分解成左子树与右子树两部分，同时postorder在根节点之前紧接的一串是右子树，再剩下的最前面一串就是左子树。

Q3 #215 Kth Largest Element in an Array 寻找数组中第K个最大元素

解题思路： 最直接的方法就是先对数组进行快速排序，然后取array[k-1]就行。时间复杂度是O(nlogn)，还能接受。