Binary Tree

树：Tree

遍历

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

后序结果可由前序改变入栈顺序，翻转结果数组得来。**但这种方法不是真正意义上的后序遍历:左—>右->中** 。但是其实遍历本来就要用root节点做媒介，也先访问了root节点。

遍历题目

前中后序

递归和迭代的写法.

• 144. 二叉树的前序遍历
• 94. 二叉树的中序遍历
• 145. 二叉树的后序遍历

遍历应用

• 513. 找树左下角的值
• 129. 求根节点到叶节点数字之和
• 285. 二叉搜索树中的中序后继
• 426. 将二叉搜索树转化为排序的双向链表
• 113. 路径总和 II
• 437. 路径总和 III

层序遍历

• 116. 填充每个节点的下一个右侧节点指针
• 117. 填充每个节点的下一个右侧节点指针 II
• 103. 二叉树的锯齿形层序遍历
• 114. 二叉树展开为链表

特殊种类

• 满二叉树
• 完全二叉树
• 二叉搜索树
• 平衡二叉树
• 平衡二叉搜索树

善用特殊树各种性质解题

完全二叉树

• 222. 完全二叉树的节点个数

平衡二叉树

• 110.平衡二叉树

二叉搜索树

inOrder有序

• 700. 二叉搜索树中的搜索
• 98.验证二叉搜索树
• 530. 二叉搜索树的最小绝对差
• 501. 二叉搜索树中的众数
• 235. 二叉搜索树的最近公共祖先
• 701. 二叉搜索树中的插入操作
• 450. 删除二叉搜索树中的节点
• 669. 修剪二叉搜索树
• 108. 将有序数组转换为二叉搜索树
• 538. 把二叉搜索树转换为累加树
• 1382. 将二叉搜索树变平衡 : 旋转？？
• 96. 不同的二叉搜索树(dp)
• 653. 两数之和 IV - 输入 BST(考虑树双指针双栈实现)Morris+双指针 ： defer
• 783. 二叉搜索树节点最小距离

构造

遍历构造

迭代法值得考究

• 105. 从前序与中序遍历序列构造二叉树
• 106. 从中序与后序遍历序列构造二叉树

数组构造

• 654. 最大二叉树 单调栈 tricky
• 108. 将有序数组转换为二叉搜索树

链表构造

• 109. 有序链表转换二叉搜索树

深度

• 104. 二叉树的最大深度
• 111. 二叉树的最小深度

递归妙解

• 814. 二叉树剪枝
• 236. 二叉树的最近公共祖先

其他操作

• 226. 翻转二叉树
• 156. 上下翻转二叉树
• 101. 对称二叉树 做一下迭代
• 257. 二叉树的所有路径
• 404. 左叶子之和
• 617. 合并二叉树
• 543. 二叉树的直径
• 863. All Nodes Distance K in Binary Tree

插入、删除通常需要用到返回值!!!

hard

• 968. 监控二叉树
• 297. 二叉树的序列化与反序列化
• 572. 另一棵树的子树 ：树哈希和树上字符串匹配

树形DP

题型

• 124. 二叉树中的最大路径和

• 二叉树中找连通块的最大值（Acwing题目）

• 687. 最长同值路径

• 968. 监控二叉树 类似这题，用返回值告诉子节点状态。

未归档

1382. 将二叉搜索树变平衡 ：遍历 + 构造，没看到高阶解法。