654.最大二叉树
题目链接：https://leetcode.cn/problems/maximum-binary-tree/submissions/
解答：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
1. 确定递归函数的参数和返回值
参数传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型TreeNode。
2. 确定终止条件
题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。
那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回
3. 确定单层递归的逻辑
这里有三步工作
先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
最大值所在的下标左区间 构造左子树：这里要判断maxValueIndex > 0，因为要保证左区间至少有一个数值
最大值所在的下标右区间 构造右子树：判断maxValueIndex < (nums.size() - 1)，确保右区间至少有一个数值
优化
通过下标索引直接在原数组上操作
可以发现上面的代码看上去简洁一些，主要是因为优化后是允许空节点进入递归，所以不用在递归的时候加判断节点是否为空
第二版代码是允许空节点进入递归，所以没有加if判断，当然终止条件也要有相应的改变。
第一版终止条件，是遇到叶子节点就终止，因为空节点不会进入递归。
第二版相应的终止条件，是遇到空节点，也就是数组区间为0，就终止了。
617.合并二叉树
题目链接：https://leetcode.cn/problems/merge-two-binary-trees/submissions/
700.二叉搜索树中的搜索
题目链接：https://leetcode.cn/problems/search-in-a-binary-search-tree/submissions/
递归：
因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。
如果root.val > val，搜索左子树，如果root.val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。
⚠️写递归函数的时候 习惯直接写 searchBST(root->left, val)，却忘了 递归函数还有返回值
迭代：
对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，再走右分支。
而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。
98.验证二叉搜索树
题目链接：https://leetcode.cn/problems/validate-binary-search-tree/
递归
1. 可以递归中序遍历将二叉搜索树转变成一个数组, 然后只要比较一下，这个数组是否是有序的，注意二叉搜索树中不能有重复元素!(用小于等于）
2. 不用转变成数组，可以在递归遍历的过程中直接判断是否有序：
⚠️：
1. 不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了
2. 样例中最小节点 可能是int的最小值，如果这样使用最小的int来比较也是不行的。此时可以初始化比较元素为longlong的最小值。
注意递归函数要有bool类型的返回值，只有寻找某一条边（或者一个节点）的时候，递归函数会有bool类型的返回值。其实本题是同样的道理，我们在寻找一个不符合条件的节点，如果没有找到这个节点就遍历了整个树，如果找到不符合的节点了，立刻返回。
如果是空节点 是不是二叉搜索树呢? 是的，二叉搜索树也可以为空！
中序遍历，一直更新maxVal，一旦发现maxVal >= root->val，就返回false，注意元素相同时候也要返回false。
优化：
建议避免 初始化最小值，如下方法取到最左面节点的数值来比较。
TreeNode pre = null; （放在函数外 全局变量）
if (pre !=null && pre.val>=root.val) return false;
pre = root;
