汇总|打遍天下二叉树
其实一些二叉树的问题中,大多数题目是有规律可循的。所以打算总结一下。
ps: 文中的所有代码均可在 https://github.com/xfhy/Algorithms 中找到.。该项目有一些关于二叉树的基本学习代码和二叉树的题解等。
01
基本概念
文中的二叉树节点定义如下:
02
深度优先遍历
2.1 递归方式
递归的方式实现深度优先遍历代码较简洁,一般只需要几行代码即可。
用递归来实现深度优先遍历是只是输出的执行位置不同。下面我们来看下代码:
2.2 非递归方式
绝大多数可以用递归解决的问题,同样也可以用栈来解决。它们都有回溯的特性。
首先来看前序遍历,实现非递归方式前序遍历的思路:
先用一个栈来记录访问过的节点
然后从根节点开始往左节点遍历,一直往下,直到左边没有左节点
接着弹栈,继续访问弹出的这个元素的右节点。如果这个右节点有左子树的话,把当前节点当做根节点,继续重复2步骤
一直到把所有元素都遍历完成
然后我们来看中序遍历,在前序遍历的基础上,只需要稍等改动一下sout的位置即可。
从根节点开始找二叉树的最左节点,找到最左节点后访问,对于每个节点来说,它都是以自己为根的子树的根节点,访问完之后就可以转到右儿子上了。
后续遍历就稍微复杂点,其实也只需要在先序遍历的基础上稍微改改就OK。
先序是:中前后,改一下while中的左右压栈，顺序就是: 中后前,得到数据之后再反转,即:前后中就得到了最后的结果。
03
广度优先遍历
即按照高度顺序一层一层的访问整棵树,高层次节点将会比低层次节点先被访问到。下面来看一下用代码怎么实现二叉树的层序遍历,这里需要用到一个队列，将根节点入队：
04
案例
4.1 二叉树的最大深度
根节点的最大深度=左节点最大深度+右节点最大深度+1
这就非常适合递归,直接递归即可。
4.2 记录每一层的所有元素
有时候我们需要记录每一层上的所有元素,这时我们可以在上面二叉树层序遍历的基础上,稍稍改进一下即可:
遍历一层的时候,先记录这层的元素个数,再依次添加到记录的集合中,顺便把这些元素的左右节点入队，继续遍历下一层。
以上就是本次推文的全部内容，如果您身边的朋友也需要请帮忙转发给TA~
文末福利
