特别说明
题目1.普通二叉树上寻找两个节点的最近公共祖先
注意
著名的 lca 问题，非常重要的问题
- Tarjan 算法解决 lca 的批量查询
- 树链剖分算法解决 lca 的在线查询（不断增删节点）
会在【扩展】课程讲述
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）”
测试链接
答案
题目2.搜索二叉树上寻找两个节点的最近公共祖先
题目3.收集累加和等于 aim 的所有路径
测试链接
思路
回溯：递归恢复现场
答案
题目4.验证平衡二叉树(树型 dp 沾边)
题目描述
给定一个二叉树，判断它是否是高度平衡的二叉树。
平衡二叉树：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1
测试链接
答案
题目5.验证搜索二叉树(树型 dp 沾边)
题目描述
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数
- 节点的右子树只包含 大于 当前节点的数
- 所有左子树和右子树自身必须也是二叉搜索树
测试链接
答案
题目6.修剪搜索二叉树
题目描述
给你二叉搜索树的根节点 root ，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在 [low, high] 中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
测试链接
答案
题目7.二叉树打家劫舍问题(树型 dp 沾边)
测试链接
答案
备注
数组的打家劫舍问题变形很多，会在【必备】课程的动态规划大章节部分讲述