赞
踩
由于平时喜欢用LGB做数据挖掘,所以就先从二叉树开始熟悉一下leetcode。本文总结一下leetcode的二叉树类型
方法
模版
主要是前中后、层序遍历
此类题目返回的是一棵树。构建时需要先构建root,再left 和right。
那么构建linked list的题目其实就是构建node和next。但是在已有树时,可以从tail或top
典型题目从preorder和inorder恢复二叉树等。
106中,虽然注意了递归。也要却要注意先生成右子树,再生成左子树的顺序,否则报错节点不存在。因为写法里有关于后续的pop,只有右子树的pop完之后剩下的才都是左子树节点
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not inorder or not postorder:
return
root = TreeNode(postorder.pop(-1))
index = inorder.index(root.val)
root.right = self.buildTree(inorder[index+1:], postorder)
root.left = self.buildTree(inorder[: index], postorder)
return root
这题还是很综合的,有树的构建、有BST、还有类似回溯的permuattion。
108 https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
根据审题可知,要构建一颗高度平衡的BST。所以就要利用性质,而且构建树的时候都要先构建root其实,再利用BST的性质找到root,也就是中位数。
109 https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
和108思路类似,构建树需要先从root开始,然后左右。而bst的root是中位数,array可以直接根据位置得到,list则可以根据快慢指针得到
此类题目用的是dfs或回溯在树中的应用
还有一类是针对BST中序的题目。有时候先遍历完根据排序性质判断反而更简单,在遍历过程中进行操作比较难想
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。