链表与树是面试中出现频率最高的数据结构。
链表之所以频率比较高，是因为在面试那中时长控制下，时间上是不允许面试官有太多的时间考察算法题，所以一些高难度的算法题一般都是说出一些思路或者写出核心算法就好，而难度太低的数组和字符串考察难度太低而被很多面试官选择性的放弃，再说链表这种数据结构，结构简单，但是可以考察的点会很多，简单点的像写出链表的插入和删除方法，难点的直接一道相关算法题，但是整体的代码量都不是很大，难度也不会很简单。整体来说之所以面试考察的比较频繁，就是因为代码量少而精，有一定难度从而有了一定的筛选度，作为动态数据结构能考察面试者的代码功底，所以被选择作为面试中算法考察必备题目之一。
链表的考法有很多，作者在书中举了很多的例子，比如链表逆置，删除一个节点，删除倒数第k个节点，反转链表，合并两个排序的链表，两个链表的第一个公共节点，环形链表，双向链表，复杂链表等
这里作者给出了一个比较简单的例子，可以感受下链表做题感觉。
面试题6：从尾到头打印链表_文选的blog-CSDN博客
二叉树：二叉树的数据结构长的样子大家都明白，面试的话基础就是先中后序的遍历方法，二叉树为什么大家都喜欢考，原因可能是代码短小适合在面试短时间内考察，而且考这一个就顺手考察了链表，或者为了考而考，算法题中很多，但是实际上项目代码中使用的并不太多（红黑树那个梗）。
首先是二叉树的结点，就是上面双向链表的节点：
class ListNode(object):
def __init__(self, x=None, left=None, right=None):
self.left = left
self.val = x
self.right = right
因为本身二叉树就是一种递归的数据结构，创建和读取都可以用递归的方式完成
二叉树的特点就是
1.除了根节点，所有的节点都有父节点；
2.除了叶子节点，所有的节点都有子节点；
3.二叉树中，第 i 层最多有 2的i次方-1 个结点；
4.如果二叉树的深度为 K，那么此二叉树最多有 2的K次方-1 个结点；
5.
6.
简单了解下就好，下面重点就是这先中后序遍历的递归和非递归写法
先序遍历：
就是先访问节点，再访问左子节点，最后访问右子节点
比如这个
这个二叉树的遍历结果就是：
先序遍历：A-B-D-G-C-E-F
中序遍历：D-G-B-A-E-C-F
后序遍历：G-D-B-E-F-C-A
一个小问题：代码中如何创建一颗二叉树，二叉树的创建方法有很多，二叉树如果比较简单的话，通过手工创建即可，数量比较大或者在编程中遇到，还是需要去创建的，这里先简单提一种创建二叉树的方法
首先的问题是，根据一个先序遍历的结果是无法找到一个准确的二叉树的，所以这里需要把结果补充完整，比如这里的先序遍历结果是A-B-D-G-C-E-F，将叶子节点的左右空节点用#来表示，树中空出的节点也用#表示，就可以将对应的二叉树转换成一种扩展的二叉树，这里的话对应的扩展二叉树的先序遍历结果就是A-B-D-#-G-#-#-#-C-E-#-#-F-#-#
当然这种算法本身也是一种递归算法，所以就要找出它的对应的递归实现条件：
1. 递归的出口：结果中没有值了
2. 递归每次实现的功能是什么：创建一个根节点和两个子节点
3. 递归返回值：返回本层中创建好的root节点
所以二叉树的先序递归创建代码就是这样的：
class ListNode(object):
def __init__(self, x=None, left=None, right=None):
self.left = left
self.val = x
self.right = right
def newBinaryTree(root,nums):
if len(nums) == 0:
return
if nums[0] != "#":
root = ListNode(nums.pop(0))
root.left = newBinaryTree(root.left,nums)
root.right = newBinaryTree(root.right,nums)
return root
else:
root = None
nums.pop(0)
return root
nums = list("ABD#G###CE##F##")
root = newBinaryTree(None,nums)
创建好之后，我们可以用先中后序的方法依次遍历下这个创建好的二叉树，验证下上述代码创建的二叉树正确性
三种递归遍历
def preOrder(root): #先序遍历
if root == None:
return
print (root.val)
preOrder(root.left)
preOrder(root.right)
def inOrder(root): # 中序遍历
if root == None:
return
inOrder(root.left)
print (root.val)
inOrder(root.right)
def postOrder(root): # 后序遍历
if root == None:
return
inOrder(root.left)
inOrder(root.right)
print (root.val)
三种非递归遍历
def preOrderNorecur(root): # 先序遍历非递归
if root == None:
return
stack = [root]
while stack:
s = stack.pop()
if s:
print(s.val)
stack.append(s.right)
stack.append(s.left)
def inOrderNorecur(root): # 中序遍历非递归
if root == None:
return
stack = []
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
print(root.val)
root = root.right
def postOrderNorecur(root): # 后序遍历非递归
if root == None:
return
stack = []
while stack or root:
while root: # 下行循环，直到找到第一个叶子节点
stack.append(root)
if root.left: # 能左就左，不能左就右
root = root.left
else:
root = root.right
s = stack.pop()
print(s.val)
#如果当前节点是上一节点的左子节点，则遍历右子节点
if stack and s == stack[-1].left:
root = stack[-1].right
else:
root = None
还有一种层次遍历，一般面试不会问，可以了解一下，就是从上到下从左到右输出当前的二叉树，上图所示的二叉树的层次遍历结果就是：A-B-C-D-E-F-G
代码实现就是：
def BFS(root):
queue = [root]
while queue:
n = len(queue)
for i in range(n):
q = queue.pop(0)
if q:
print(q.val)
queue.append(q.left if q.left else None)
queue.append(q.right if q.right else None)
除了最上面说的通过扩展的方法来重建二叉树，也可以通过先序和中序遍历重建二叉树，比如会由这样的面试题，（对应的说lc的 重建二叉树 ）
根据给出的先序和中序遍历结果，重建二叉树（已知没有重复元素）：
先序遍历 1，2，4，7，3，5，6，8
中序遍历 4，7，2，1，5，3，8，6
看到这种面试题，首先要知道二叉树的性质，比如二叉树的先序遍历结果中，第一个肯定是root，而中序遍历的结果，根节点在中间，也就是说 4 7 2为左子树，5 3 8 6为右子树
所以程序的第一步就是找到左子树，右子树以及根节点
# -*- coding:utf-8 -*-
class ListNode(object):
def __init__(self, x=None, left=None, right=None):
self.left = left
self.val = x
self.right = right
def rebuildBinaryTree(list_preorder,list_inorder):
root = list_preorder[0]
root_index = list_inorder.index(root)
list_leftbinary = list_inorder[:root_index]
list_rightbinary = list_inorder[root_index:]
list_preorder = [1,2,4,7,3,5,6,8]
list_rightbinary = [4,7,2,1,5,3,8,6]
rebuildBinaryTree(list_preorder,list_inorder)
实际上现在关于左子树和右子树，又可以分别看成两个二叉树，因为本身二叉树就是递归的，所以从这里可以看出来，这道题实际上还是递归的解法比较简单
# -*- coding:utf-8 -*-
class TreeNode(object):
def __init__(self, x=None, left=None, right=None):
self.left = left
self.val = x
self.right = right
def myBuildTree(preorder_left, preorder_right, inorder_left, inorder_right):
if preorder_left > preorder_right:
return None
# 前序遍历中的第一个节点就是根节点
preorder_root = preorder_left
# 在中序遍历中定位根节点
inorder_root = index[preorder[preorder_root]]
# 先把根节点建立出来
root = TreeNode(preorder[preorder_root])
# 得到左子树中的节点数目
size_left_subtree = inorder_root - inorder_left
# 递归地构造左子树，并连接到根节点
# 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
root.left = myBuildTree(preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1)
# 递归地构造右子树，并连接到根节点
# 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
root.right = myBuildTree(preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right)
return root
preorder = [1,2,4,7,3,5,6,8]
inorder = [4,7,2,1,5,3,8,6]
n = len(preorder)
# 构造哈希映射，帮助我们快速定位根节点
index = {element: i for i, element in enumerate(inorder)}
myBuildTree(0, n - 1, 0, n - 1)
不解释了，背过吧。。。真心不知道面试官自己有没有写过几个二叉树的。。。。
作者在这里，提了两道比较基础的题
