剑指报价（Java版）day05

【标题】从上至下打印二叉树的每个节点，从左至右打印同一层的节点.

[检查点]通过示例进行具体的抽象；二叉树

【思考】使用ArrayList创建两组，一组存储每个节点的值，一组模仿堆栈，然后按从上到下二叉排序树的遍历，从左到右的顺序将节点推入堆栈.

[错误1]第一个集合类型为二叉排序树的遍历，第二个集合类型为，请确保不要出错〜

[错误2]第二组只是模仿堆栈，但我伪造了它并将其用作堆栈，并称为堆栈方法. .

[代码]

2二叉搜索树的后遍历序列

【标题】输入一个整数数组，以确定该数组是否是遍历二叉搜索树的结果. 如果是，则输出“是”，否则输出“否”. 假设输入数组中的任何两个数字互不相同.

[检查点]通过示例进行具体的抽象；二叉树

[思考] BST序列的合法序列是序列S的最后一个元素是x（即根）. 如果最后一个元素的序列为T，则T满足: T可分为两部分: 分段，前一个分段（左子树）小于x，后一个分段（右子树）大于x，并且两个分段（子树）是合法的后置顺序. 每次删除序列的最后一个元素，并且将前一个元素分为两部分以继续递归.

[错误1]递归时必须弄清两个元素的开始和结束位置. 在正确之前已对其进行了多次更改.

【错误2】请记住，序列的最后一个元素不参与循环或递归，因为它是当前的根元素.

[错误3]递归结束的条件之一是（start 我也发现问题很长时间了. .

【提示】在不清楚的情况下自己编写一个测试用例，与用例一起编写想法会更加清晰！

[代码]

【想法】递归！如果当前根节点不为null，则将其添加到a序列中. 每次递归到叶节点后，都应删除序列a中的最后一个节点，以便返回上层并继续查找其他路径.

[检查点]通过示例进行具体的抽象；二叉树

[错误1]请注意复习问题. 从根节点到叶节点仅计算一条路径，因此将a加到全部有三个条件.

[错误2]遍历节点的所有子节点后，有必要删除a中的当前节点. 这是非常关键的一步.

【关键字】递归特别容易引起混乱. 我特意画了一个递归过程的图片，以便使思路很清晰:

[代码]

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-241256-1.html