1.樹是真的麻煩啊饿序！
我認為勉失，樹是鏈表的一種“變形”，從單鏈表的一個指針原探，變成了二叉樹的左右兩根指針乱凿。
它一衍生就成了圖顽素，然后還能應用在堆上，真的博大精深徒蟆。
但就是太難了胁出。
首先，常規(guī)操作：我先自己實現(xiàn)了下樹段审。
https://github.com/Wind0ranger/LeetcodeLearn/blob/master/5-tree/Tree.py
簡單說一下：
- 構建樹的時候：這里的樹全蝶，我是由字典保存的。然后通過兩次循環(huán)構建成樹的寺枉。第一層循環(huán)是為了建立節(jié)點抑淫，第二層循環(huán)是為了鏈接左右節(jié)點。
@classmethod
def build_from(cls, node_list):
"""通過節(jié)點信息構造二叉樹
第一次遍歷我們構造 node 節(jié)點
第二次遍歷我們給 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
