一、如何利用二叉樹(shù)的前序，中序遍歷確定后序遍歷
二叉樹(shù)是一種常用的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和編程中。其中，前序遍歷、中序遍歷和后序遍歷是三種常見(jiàn)的二叉樹(shù)遍歷方式。前序遍歷是先訪(fǎng)問(wèn)根節(jié)點(diǎn)，然后遞歸地遍歷左子樹(shù)和右子樹(shù)；中序遍歷是先遞歸地遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根節(jié)點(diǎn)，最后遞歸地遍歷右子樹(shù)；后序遍歷是先遞歸地遍歷左子樹(shù)和右子樹(shù)，然后訪(fǎng)問(wèn)根節(jié)點(diǎn)。
1、確定根節(jié)點(diǎn)
前序遍歷結(jié)果的名列前茅個(gè)元素一定是二叉樹(shù)的根節(jié)點(diǎn)。
2、在中序遍歷結(jié)果中找到根節(jié)點(diǎn)的位置
根據(jù)前序遍歷中確定的根節(jié)點(diǎn)，在中序遍歷結(jié)果中找到對(duì)應(yīng)的位置，將中序遍歷結(jié)果分成左子樹(shù)和右子樹(shù)兩部分。
3、遞歸處理左子樹(shù)
利用前序遍歷和中序遍歷結(jié)果，對(duì)左子樹(shù)進(jìn)行遞歸處理，得到左子樹(shù)的后序遍歷。
4、遞歸處理右子樹(shù)
利用前序遍歷和中序遍歷結(jié)果，對(duì)右子樹(shù)進(jìn)行遞歸處理，得到右子樹(shù)的后序遍歷。
5、拼接結(jié)果
將左子樹(shù)的后序遍歷、右子樹(shù)的后序遍歷和根節(jié)點(diǎn)拼接在一起，得到最終的后序遍歷結(jié)果。
京公網(wǎng)安備 11010802030320號(hào)