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

題目描述：根據(jù)一棵樹(shù)的中序遍歷與后序遍歷構(gòu)造二叉樹(shù)。

注意: 你可以假設(shè)樹(shù)中沒(méi)有重復(fù)的元素。

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

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

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

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

解法一：遞歸

根據(jù)中序遍歷和后序遍歷的性質(zhì)，通過(guò)遞歸的方式求解，遞歸的過(guò)程如下：

• 首先，如果中序遍歷序列或后序遍歷序列為空，直接返回空樹(shù)；

• 因?yàn)楹笮虮闅v序列的最后一個(gè)值為根節(jié)點(diǎn)，所以首先根據(jù)這個(gè)初始化得到當(dāng)前的根節(jié)點(diǎn)root；

• 然后根據(jù)根節(jié)點(diǎn)root在中序遍歷序列中的位置，根節(jié)點(diǎn)前面的值都是當(dāng)前根節(jié)點(diǎn)的左子樹(shù)節(jié)點(diǎn)，得到當(dāng)前根節(jié)點(diǎn)左右子樹(shù)節(jié)點(diǎn)的數(shù)量；

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

• 最后返回root即為還原后的樹(shù)。

【每日寄語(yǔ)】 命運(yùn)負(fù)責(zé)洗牌，但是玩牌的是我們自己！