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. 確定遞歸函數(shù)的參數(shù)和返回值
參數(shù)傳入的是存放元素的數(shù)組，返回該數(shù)組構(gòu)造的二叉樹的頭結(jié)點斩松，返回類型TreeNode伶唯。
2. 確定終止條件
題目中說了輸入的數(shù)組大小一定是大于等于1的，所以我們不用考慮小于1的情況惧盹，那么當(dāng)遞歸遍歷的時候乳幸，如果傳入的數(shù)組大小為1，說明遍歷到了葉子節(jié)點了岭参。
那么應(yīng)該定義一個新的節(jié)點反惕，并把這個數(shù)組的數(shù)值賦給新的節(jié)點，然后返回這個節(jié)點演侯。 這表示一個數(shù)組大小是1的時候，構(gòu)造了一個新的節(jié)點背亥，并返回
3. 確定單層遞歸的邏輯
這里有三步工作
先要找到數(shù)組中最大的值和對應(yīng)的下標(biāo)秒际， 最大的值構(gòu)造根節(jié)點，下標(biāo)用來下一步分割數(shù)組狡汉。
最大值所在的下標(biāo)左區(qū)間 構(gòu)造左子樹：這里要判斷maxValueIndex?>?0娄徊，因為要保證左區(qū)間至少有一個數(shù)值
最大值所在的下標(biāo)右區(qū)間 構(gòu)造右子樹：判斷maxValueIndex?<?(nums.size()?-?1)，確保右區(qū)間至少有一個數(shù)值
優(yōu)化
通過下標(biāo)索引直接在原數(shù)組上操作
可以發(fā)現(xiàn)上面的代碼看上去簡潔一些盾戴，主要是因為優(yōu)化后是允許空節(jié)點進(jìn)入遞歸寄锐，所以不用在遞歸的時候加判斷節(jié)點是否為空
第二版代碼是允許空節(jié)點進(jìn)入遞歸，所以沒有加if判斷，當(dāng)然終止條件也要有相應(yīng)的改變橄仆。
第一版終止條件剩膘，是遇到葉子節(jié)點就終止，因為空節(jié)點不會進(jìn)入遞歸盆顾。
第二版相應(yīng)的終止條件怠褐，是遇到空節(jié)點，也就是數(shù)組區(qū)間為0您宪，就終止了奈懒。
617.合并二叉樹?
題目鏈接：https://leetcode.cn/problems/merge-two-binary-trees/submissions/
700.二叉搜索樹中的搜索?
題目鏈接：https://leetcode.cn/problems/search-in-a-binary-search-tree/submissions/
遞歸：
因為二叉搜索樹的節(jié)點是有序的，所以可以有方向的去搜索宪巨。
如果root.val?>?val磷杏，搜索左子樹，如果root.val?<?val捏卓，就搜索右子樹极祸，最后如果都沒有搜索到，就返回NULL天吓。
??寫遞歸函數(shù)的時候 習(xí)慣直接寫?searchBST(root->left, val)贿肩，卻忘了 遞歸函數(shù)還有返回值
迭代：
對于一般二叉樹，遞歸過程中還有回溯的過程龄寞，例如走一個左方向的分支走到頭了汰规，那么要調(diào)頭，再走右分支物邑。
而對于二叉搜索樹溜哮，不需要回溯的過程，因為節(jié)點的有序性就幫我們確定了搜索的方向色解。
98.驗證二叉搜索樹?
題目鏈接：https://leetcode.cn/problems/validate-binary-search-tree/
遞歸
1. 可以遞歸中序遍歷將二叉搜索樹轉(zhuǎn)變成一個數(shù)組, 然后只要比較一下茂嗓，這個數(shù)組是否是有序的，注意二叉搜索樹中不能有重復(fù)元素!(用小于等于）
2. 不用轉(zhuǎn)變成數(shù)組科阎，可以在遞歸遍歷的過程中直接判斷是否有序：
??：
1. 不能單純的比較左節(jié)點小于中間節(jié)點述吸，右節(jié)點大于中間節(jié)點就完事了
2. 樣例中最小節(jié)點 可能是int的最小值，如果這樣使用最小的int來比較也是不行的锣笨。此時可以初始化比較元素為longlong的最小值蝌矛。
注意遞歸函數(shù)要有bool類型的返回值，只有尋找某一條邊（或者一個節(jié)點）的時候错英，遞歸函數(shù)會有bool類型的返回值入撒。其實本題是同樣的道理，我們在尋找一個不符合條件的節(jié)點椭岩，如果沒有找到這個節(jié)點就遍歷了整個樹茅逮，如果找到不符合的節(jié)點了璃赡，立刻返回。
如果是空節(jié)點 是不是二叉搜索樹呢??是的献雅，二叉搜索樹也可以為空碉考！
中序遍歷，一直更新maxVal惩琉，一旦發(fā)現(xiàn)maxVal >= root->val豆励，就返回false，注意元素相同時候也要返回false瞒渠。
優(yōu)化：
建議避免 初始化最小值良蒸，如下方法取到最左面節(jié)點的數(shù)值來比較。
TreeNode pre = null; （放在函數(shù)外 全局變量）
if (pre !=null && pre.val>=root.val) return false;
pre = root;
