從前序與中序遍歷序列構(gòu)造二叉樹

題目描述：給定一棵樹的前序遍歷 preorder 與中序遍歷 inorder。請(qǐng)構(gòu)造二叉樹并返回其根節(jié)點(diǎn)。

示例說(shuō)明請(qǐng)見LeetCode官網(wǎng)。

來(lái)源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：遞歸法

通過(guò)遞歸的方式構(gòu)造二叉樹，遞歸過(guò)程如下：

• 如果前序遍歷序列或者中序遍歷序列為空時(shí)，直接返回空樹；

• 因?yàn)榍靶虮闅v序列的第一個(gè)值為根節(jié)點(diǎn)，所以首先得到根節(jié)點(diǎn)；

• 然后根據(jù)中序遍歷中根節(jié)點(diǎn)的位置得到根節(jié)點(diǎn)的左右子樹的節(jié)點(diǎn)的數(shù)量leftCount和rightCount；

• 然后遞歸調(diào)用該方法得到當(dāng)前根節(jié)點(diǎn)的左右子樹；

• 最后返回根節(jié)點(diǎn)。

【每日寄語(yǔ)】 我的生活從艱辛到自如沒有強(qiáng)大的內(nèi)心不可為之。無(wú)人能一手成就誰(shuí)，真正的神在我心中。唯有自己努力方能見到曙光！