树作为重要的数据结构,在很多领域有着重要的用途。在LeetCode中对数的考察主要分为三个方面,一是树的遍历,二是BST(二叉搜索树),三是和树相关的算法。有时,树也常常被看做一个图,做BFS和DFS,树的考察是相当灵活的。这篇博客就这些问题做部分小结。

树的种类

参考维基百科定义,需要掌握如下概念。

完全二叉树

平衡二叉树

理想二叉树(完美二叉树)

 

树的遍历

树的遍历方法主要分为三种:先序 PreOrder,中序 InOrder, 后序 PostOrder,还有一种方式也会用到,叫做 层序 LevalOrder。

从实现上讲,上面几种方式都可以通过递归的方式和迭达方式实现,如果不是尾递归的话,空间复杂度就是O(lg(n)),所以使用迭代方式遍历树就有空间复杂度O(1)的优势,并且迭代减少了函数调用的开销(实际时间未必比递归方式少),所以下面主要讲这几种遍历方式的迭代实现。

迭代遍历

先序遍历

 

中序遍历

 

后序遍历

 

层序遍历

层序遍历就是广度优先搜索,只是注意,风格上与上面有两点不同,一是使用队列而不是栈,二是使用NULL指针标记每层的末尾节点,用来区分层次。

 

递归遍历

使用递归方式遍历树,这个大家都会,就不说了。

二叉搜索树

树的平衡性

路径搜索

最近共同祖先问题

 

挖个坑,有空填

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注