二叉树的层序遍历
题解:
使用队列来实现,定义一个结果集res,定义一个双端队列,初始化为根节点,我们示例可以看出,是两层列表嵌套,也就是说我们要在循环中还要创建一个列表tmp,列表是用来存储数据的,不是节点,记住是在循环内,原因是,每次循环之后都是要初始化的,然后处理队列中的数据,从对头弹出节点,将节点中的值存储在tmp中,然后去判断左右接地那是否为空,不为空,放入队列中。
代码:
翻转二叉树
题解:
使用前序遍历和后序遍历均可,每次先将根节点的左右子树调换位置
代码:
包含递归法和迭代法
对称二叉树
题解:
递归三部曲:
1.确定递归函数的参数和返回值
比较是根节点的两个字数是否相互反转,进而判断这个树是不是对称的,所以传参数两个子树,返回值是bool类型
2.确定终止条件
节点为空的情况:
左为空,右不为空,不对称,返回false
左不为空,右为空,不对称,返回false
左右都为空,堆成,返回true
节点不为空的情况:
左右都不为空,且值不相等,返回false