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/
这题,我想的很简单,直接中序遍历,查看是否是顺序排序。写的很差,我会修改的。今天太累了,不改了。
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
网友评论