二叉树理论基础

二叉树的种类、存储方式、遍历方式、定义方式

二叉树遍历方式

(1) 递归遍历
递归三部曲（确定递归函数参数及返回值，确定终止条件，确定单层递归逻辑）。
(2) 迭代遍历
前序：栈 根节点 →\rightarrow→ 右孩子 →\rightarrow→ 左孩子 （注意是先右后左）。
中序：栈和指针 先访问到二叉树最左边的最底部，再开始处理结点 易错点：whilewhilewhile 循环里的条件是或。
(3) 层序遍历
队列 : 注意每层都要记录队列的大小 sizesizesize。

求二叉树的属性

(1) 是否对称
后序，比较外侧和内侧是否对称。
(2) 求最大深度
递归：后序，求根节点最大高度就是最大深度，通过递归函数的返回值做计算树的高度。
迭代：层序遍历。
(3) 求最小深度
递归：后序，求根节点最小高度就是最小深度，注意最小深度的定义，处理左右结点一个为空，一个不为空的情况。
迭代：层序遍历。
(4) 求有多少个节点
递归：后序，通过递归函数的返回值计算节点数量。
迭代：层序遍历。
(5) 二叉树：是否平衡
递归：后序，注意后序求高度，通过返回值是否为 -1 判断是否平衡。
(6) 二叉树：找所有路径
递归：前序，涉及回溯处理根节点到叶子的所有路径，注意中间处理逻辑要写在递归函数的最前面。
迭代：一个栈模拟递归，一个栈来存放对应的遍历路径。
(7) 二叉树：求左叶子之和
递归：后序，要通过节点的父节点判断本节点的属性，才能判断是否是左叶子。
迭代：直接模拟后序遍历。
(8) 二叉树：求左下角的值
递归：优先左孩子搜索，同时找深度最大的叶子节点，涉及回溯。
迭代：层序遍历找最后一行最左边。
(9) 二叉树：求路径总和
递归：回溯，递归函数返回值为bool类型是为了搜索一条边，没有返回值是搜索整棵树。

二叉树的修改与构造

(1) 翻转二叉树
前序遍历，交换左右孩子结点。
(2) 根据中序和后序构造二叉树
前序，找分割点，左右构造。
(3) 最大二叉树
前序，分割点为数组最大值，分左右区间构造。
(4) 合并二叉树
前序，同时操作两棵二叉树，注意合并规则。

求二叉搜索树的属性

(1) 二叉搜索树中的搜索
二叉搜索树中的搜索是有方向的，待搜索的值小于当前结点的值往左递归，待搜索的值大于当前结点的值往右递归。
(2) 验证二叉搜索树
中序，判断是否递增，注意指针 preprepre 的应用。
(3) 二叉搜索树的最小绝对差
中序，注意指针 preprepre 的应用。
(4) 二叉搜索树中的众数
中序，注意指针 preprepre 的应用, 还有清空结果集的技巧，遍历一遍便可求众数集合。
(5) 二叉搜索树转成累加树
递归：反中序，双指针操作累加。
迭代：模拟反中序，逻辑相同。

二叉树公共祖先问题

(1) 二叉树的公共祖先问题
递归：后序，用指针 leftleftleft 和 rightrightright 接住上一层递归返回值，通过判断 leftleftleft 和 rightrightright 是否为空来确定返回值。
(2) 二叉搜索树的公共祖先问题
递归: 第一次遇到 curcurcur 节点是数值在 [p,q][p, q][p,q] 区间中，那么 curcurcur 就是 ppp 和 qqq 的最近公共祖先。
迭代：按序遍历，逻辑相同。

二叉搜索树的修改与构造

(1) 二叉搜索树中的插入操作
递归：通过递归函数返回值添加节点, 直接用 root→leftroot \rightarrow leftroot→left 或 root→rightroot \rightarrow rightroot→right 接住。
(2) 二叉搜索树中的删除操作
递归：前序，想清楚删除非叶子节点的情况, 特别注意左右孩子都不为空的情况。还要用 root→leftroot \rightarrow leftroot→left 或 root→rightroot \rightarrow rightroot→right 接住返回值。
(3) 修剪二叉搜索树
递归：前序，通过递归函数返回值删除节点。
(4) 将有序数组转换为二叉搜索树
递归：前序，数组中间节点分割，注意循环不变量。

选择遍历顺序的一些技巧

涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。但是例如单纯求深度就用前序，二叉树：找所有路径也用了前序，这是为了方便让父节点指向子节点。
求普通二叉树的属性还是要具体问题具体分析。
求二叉搜索树的属性，一定是中序了，才能利用其有序性。