1.树是真的麻烦啊！
我认为，树是链表的一种“变形”，从单链表的一个指针，变成了二叉树的左右两根指针。
它一衍生就成了图，然后还能应用在堆上，真的博大精深。
但就是太难了。
首先，常规操作：我先自己实现了下树。
https://github.com/Wind0ranger/LeetcodeLearn/blob/master/5-tree/Tree.py
简单说一下：
- 构建树的时候：这里的树，我是由字典保存的。然后通过两次循环构建成树的。第一层循环是为了建立节点，第二层循环是为了链接左右节点。
@classmethod
def build_from(cls, node_list):
"""通过节点信息构造二叉树
第一次遍历我们构造 node 节点
第二次遍历我们给 root 和 孩子赋值
:param node_list: {'data': 'A', 'left': None, 'right': None, 'is_root': False}
"""
node_dict = {}
for node_data in node_list:
data = node_data['data']
node_dict[data] = BinTreeNode(data)
for node_data in node_list:
data = node_data['data']
node = node_dict[data]
if node_data['is_root']:
root = node
node.left = node_dict.get(node_data['left'])
node.right = node_dict.get(node_data['right'])
return cls(root)
2.遍历就是用递归的方法，真的很难想。
# 先序遍历
def preorder_trav(self, subtree):
if subtree is not None:
print(subtree.data) # 递归函数里先处理根
self.preorder_trav(subtree.left) # 递归处理左子树
self.preorder_trav(subtree.right) # 递归处理右子树
# 中序遍历
def middle_trav(self, subtree):
if subtree is not None:
self.middle_trav(subtree.left) # 递归处理左子树
print(subtree.data)
self.middle_trav(subtree.right) # 递归处理右子树
# 后序遍历
def after_trav(self, subtree):
if subtree is not None:
self.after_trav(subtree.left) # 递归处理左子树
self.after_trav(subtree.right) # 递归处理右子树
print(subtree.data)
层序用的是队列LILO，先加进来的先出去。
# 层序遍历,使用队列思想不断往里面加入，不断出去．
def layer_trav_use_queue(self, subtree):
q = []
q.append(subtree)
while len(q) != 0:
cur_node = q.pop(0)
print(cur_node.data)
if cur_node.left:
q.append(cur_node.left)
if cur_node.right:
q.append(cur_node.right)
再说这题目，链接：
https://leetcode.com/problems/validate-binary-search-tree/
98-validate-binary-search-tree.png
这题，我想的很简单，直接中序遍历，查看是否是顺序排序。写的很差，我会修改的。今天太累了，不改了。
2.题解：
class Solution(object):
def isValidBST(self, root):
L1 = self.trav(root)
return L1 == sorted(set(L1))
# 中序遍历
def trav(self, root):
if root is None:
return []
return self.trav(root.left) + [root.val] + self.trav(root.right)
3.完整代码
查看链接：
https://github.com/Wind0ranger/LeetcodeLearn/blob/master/5-tree/98-validate-binary-search-tree.py
