最大二叉樹

題解：

此題目和通過前序和后序遍歷來構(gòu)造二叉樹是一樣的，1.首先我們判空數(shù)組，也是作為遞歸終止的條件。2找到數(shù)組中的最大值，以及其所在的下標(biāo)位置，3.創(chuàng)建根節(jié)點(diǎn)，切割出來左右數(shù)組，4.遞歸。5返回root根節(jié)點(diǎn)

代碼：

合并二叉樹

題解：

1.確定遞歸函數(shù)的參數(shù)和返回值

要合并的是兩個二叉樹，那么參數(shù)至少是兩個二叉樹的根節(jié)點(diǎn)，返回值就是合并后的二叉樹的根節(jié)點(diǎn)

2.確定終止條件

傳入了兩個樹，那么兩個樹都會被遍歷，如果root1 == None，兩個樹合并就是root2，反之

3，確定單層遞歸的邏輯

采用前序遍歷的方法，我們重復(fù)利用root1這個樹（root2也行），先將兩個樹的元素加起來

root1的左子樹，合并root1的左子樹 root2左子樹之后的左子樹

root1的右子樹，合并root1的右子樹 root2右子樹之后的右子樹

最終root1就是合并之后的根節(jié)點(diǎn)

二叉搜索樹中的搜索

題解：

1.確定遞歸方法的參數(shù)和返回值

傳入的是根節(jié)點(diǎn)和要搜索的值，返回的是以這個搜索樹所在的節(jié)點(diǎn)

2.確定終止條件

若root為空，或者找到了這個值的節(jié)點(diǎn)，返回root節(jié)點(diǎn)

3.確定單層遞歸邏輯

搜索二叉樹的特性：

若它的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值

若它的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值

他的左右子樹也分別為二叉搜索樹

那么此處的邏輯是：跟節(jié)點(diǎn)的值和搜索值做對比，若root.val > val，則搜索左子樹，反之搜索右子樹

代碼：

驗(yàn)證二叉搜索樹