LeetCode总结 -- 树的性质篇

树的性质推断是树的数据结构比較主要的操作,一般考到都属于非常easy的题目,也就是第一道入门题。面试中最好不能有问题,力求一遍写对。不要给面试官不论什么挑刺机会。LeetCode中关于树的性质有下面题目:
Maximum Depth of Binary Tree
Minimum Depth of Binary Tree
Balanced Binary Tree
Same Tree
Symmetric Tree

首先说说关于求树的深度的题目,最简单的是求最大深度Maximum Depth of Binary Tree,一般都是用递归实现。思路非常easy。仅仅须要对走到空结点返回0。然后其它依次按层递增。取左右子树中大的深度就可以。

Minimum Depth of Binary Tree略微复杂一点,主要是要注意由于是取左右子树小的深度,可是有一种情况是不计入深度的,就是比方左子树彻底为空时。这样的情况我们不会觉得深度就是0,由于左边并没有叶子。依照定义我们是要找叶子结点的最小深度。所以须要对于左右是否为空做一个额外的推断。

求树的深度属于简单的题目,所以假设递归实现比較快的话。面试官可能会问非递归怎么实现。假设有时间的话还是得练习一下哈。原理跟LeetCode总结 -- 树的遍历篇是一致的。

Balanced Binary Tree是求深度的一道扩展题目,基本原理还是求深度。只是须要添加的环节是推断他是不是平衡树,由于深度是我们必须维护的量,假设选用额外的布尔变量来维护是否为平衡树也能够。只是这里能够利用深度大于0的性质,能够将平衡的树返回正常的深度值,而不平衡的则返回-1来进行区分。这样相当于用一个变量维护了想要的两种性质,代码实现也比較简单。

Same Tree也是比較基础的题目。和树的遍历时一样的,仅仅是对两棵树同一时候做同样的遍历,然后进行一一比較,假设出现不同则返回false就可以。

Symmetric Tree会略微绕一点。只是想清楚跟Same Tree还是差点儿相同。第一个不同点是要依据左右子树比較,事实上就是把左右子树当成Same Tree中的两个树就可以。第二个不同点是在递归过程中对于结点的左右子树进行互换比較,也就是左跟右比,右跟左比。

这篇总结主要提到了LeetCode中求树的一些基本性质的题目,这类题目比較简单,属于最低门槛题目,所以要力求bug free地一遍完毕哈。










本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5095806.html,如需转载请自行联系原作者

上一篇:Java 知识点总结篇(1)


下一篇:“云计算”和“大数据”成为中国公民科学素质基准