剑指offer之搜索回溯

今天刷的动态规划比较简单，正好刚开始写博客，就把前两天的搜索回溯的算法整理一下，基本上都是二叉树相关的题。

从上到下打印二叉树 I-III

1. 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。 难度：中等。

队列结构，先进先出，每次把一个节点pop出的时候，就将其左右子节点push进去。

• 时间复杂度O(N);
• 空间复杂度O(N)。

2. 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。 难度：简单。

较上一题不同的是 需要记录二叉树每一層的节点个数。具体方法就是 把上一层的节点全部pop出去之后，记录下队列的size，以这个size来引导循环。

• 时间复杂度O(N);
• 空间复杂度O(N) 。

3. 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

较上一题不同的是，在每行打印的时候需要交叉顺序打印节点。具体方法就是 建立一个bool变量 来确定这一层是正序打印还是逆序打印，每打印一层就否自己一下。

另外，如何利用该变量打印有小讲究。每层的循环操作中 除了需要push左右节点，pop掉队列中原有节点外，还需要构建出result中的该层所对应的行vector。

vec[jud?i:l-i-1] = node->val;

* 时间复杂度O(N); * 空间复杂度O(N)。

二叉树的子结构、镜像、对称

1. 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

总体想法：递归。如果该节点与B节点的值不相等，则以同样的方法将其左右节点与B节点比较；如果出现相等的情形，就下去比较各自的左右节点。

即两层递归。外层为搜索递归，内层为比较递归。 搜索时 各个条件相|| ； 比较时 各个条件相 &&。

• 时间复杂度O(MN);
• 空间复杂度O(M)。

2. 请完成一个函数，输入一个二叉树，该函数输出它的镜像。

思考如何使空间复杂度为O(1)。

具体方法： 递归。递归交换左右节点。

3. 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

双指针，递归。往方向相反的两个方向向下搜索比较。

• 时间复杂度O(N);
• 空间复杂度O(N)。