[刷题]二叉树专题

参考

1. [Leetcode 105] (剑指OFFER面试题 7)
   解法：递归，由先序序列确定子树根节点，由中序序列确定当前节点下的子树范围。
   主要参数(递归函数)：先序序列的起点idx与终点idx， 中序序列的起点idx与终点idx。
   递归停止条件： 先序序列或中序序列的起点idx > 终点idx。
   递归参数更新方法：
   左子树更新:
   先序起点idx+1。 preL + 1
   先序终点为中序确定左子树节点数量num + 先序起点idx。 preL + num
   中序起点为之前递归层中的中序起点。 inL
   中序终点为根节点在中序序列中的idx - 1。 inRoot - 1

右子树更新:
先序起点idx+1 + 中序确定左子树节点数量num。 preL + num + 1
先序终点为之前递归层中的先序终点。 preR
中序起点为根节点在中序序列中的idx + 1。 inRoot + 1
中序终点为为之前递归层中的中序终点。 inR

2. [Leetcode 572] (剑指Offer面试题 26)
   解法：递归寻根相同，根相同后判断子树是否相同。

注意：停止条件，空指针处理

代码：

3. [LeetCode 144]
   解法：

递归，先输出再递归

循环，用栈模拟，节点右子节点入栈，左节点直接输出。

代码：

4. [LeetCode 94]
   解法：

递归：遍历左节点后输出值

循环：

代码：

5. [Leetcode 145]
   解法：递归/循环，循环解，先左插，再右插，遇到空节点出栈，出栈元素插在结果数组的最前面。

代码:

5. [LeetCode 226] (剑指Offer面试题27)
   解法：递归换序

代码：

6.[LeetCode 101] (剑指Offer面试题28)
解法1： 递归，

解法2：BFS循环

7. [Leetcode 102] (剑指Offer面试题32)
   思路：用一个队列nodeQ维护二叉树BFS顺序，由于题目中需要分层记录，所以需要维护每一层的数据vectorlayerRes以及每一层可扩展节点队列layerQ。

代码：

8. [Leetcode 230]
   解法: 循环模拟中序遍历

代码: