🍎 进阶练习
226. 翻转二叉树(迭代法(用栈、队列)、递归)
590. N 叉树的后序遍历(前序遍历的逆过程,但有些细节需要注意)
101. 对称二叉树(迭代法、递归)
222. 完全二叉树的节点个数(二分查找 + 位运算、广度优先遍历、迭代)
257. 二叉树的所有路径(含回溯)
106. 从中序与后序遍历序列构造二叉树(熟悉掌握中序遍历和后序遍历)
🍃 具体实例分析
1、226. 翻转二叉树(参考)
1)问题描述
2)分析
3)代码实现
1)问题描述
2)问题分析
✨记住前序遍历是 中左右,而在迭代过程中,一轮循环的结果是“上一层栈元素出栈”以及“该层元素进栈”,结合前序遍历的性质,所以在循环中让n叉树的孩子节点从右往左进栈,这样在下一轮循环的出栈中就能保证从左往右的出来的。
3)代码实现
1)问题描述
2)分析
用栈依次存储左右节点(从两边像中间存储),然后每次出队两个节点进行比较
3)代码实现
✨思考:为什么当左右两边都是NULL的时候,是continue而不是return true;
1)问题描述
2)分析
✨方法一(深度优先暴力匹配算法)
1)问题分析
2)分析(参考)
3)代码实现
1)问题分析
2)分析(参考)
递归中隐藏着回溯。
3)代码实现
3.1)深度优先遍历方法
3.2)广度优先遍历方法
我们维护一个队列,存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中,我们取出队列中的首节点,如果它是叶子节点,则将它对应的路径加入到答案中。如果它不是叶子节点,则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜索结束,我们即能得到答案。
1)问题描述
2)分析
我们都知道后序遍历的最后一个元素是根节点,在中序遍历中,根节点则划分左右两棵子树。
通过此思想,通过递归,更新后序后序遍历的“根节点”,通过中序遍历来给这个“根节点”找它的左右子树。
3)代码实现
8、