【題目描述】
Given inorder and postorder traversal of a tree, construct the binary tree.
Notice:You may assume that duplicates do not exist in the tree.
根據(jù)中序遍歷和后序遍歷樹(shù)構(gòu)造二叉樹(shù)
注意:你可以假設(shè)樹(shù)中不存在相同數(shù)值的節(jié)點(diǎn)
【題目鏈接】
www.lintcode.com/en/problem/construct-binary-tree-from-inorder-and-postorder-traversal/
【題目解析】
本題在屬于二叉樹(shù)遍歷的經(jīng)典題目，已知二叉樹(shù)的兩個(gè)遍歷序列構(gòu)造二叉樹(shù)，有如下性質(zhì)：
若已知先序和中序诅愚，則可以構(gòu)造出唯一的二叉樹(shù)
若已知先序和后序，則可以構(gòu)造出多顆不同的二叉樹(shù)
若已知中序和后序宠哄，則可以構(gòu)造出唯一的二叉樹(shù)
本題中我們已知的條件為中序遍歷和后序遍歷，所以我們一定可以構(gòu)造出唯一的二叉樹(shù)嗤攻。
我們先將整棵樹(shù)看作根節(jié)點(diǎn)和兩顆子樹(shù)毛嫉，則其兩種遍歷得到的序列為
序列
可以肯定后序遍歷序列中最后一個(gè)數(shù)一定是當(dāng)前二叉樹(shù)的根節(jié)點(diǎn)root。又因?yàn)槎鏄?shù)不存在相同的數(shù)妇菱，我們可以找到root在中序遍歷中位置p承粤。
則我們可以分別找到兩顆子樹(shù)對(duì)應(yīng)的中序和后序遍歷：
左子樹(shù)的中序= inOrder[1 .. p - 1]
左子樹(shù)的后序= postOrder[1 .. p - 1]
右子樹(shù)的中序= inOrder[p + 1 .. n]
右子樹(shù)的后序= postOrder[p .. n - 1]
在此基礎(chǔ)上我們就可以遞歸處理兩顆子樹(shù)惊畏。
當(dāng)我們發(fā)現(xiàn)當(dāng)前中序遍歷和后序遍歷長(zhǎng)度都為1的時(shí)候，也就找到了葉子節(jié)點(diǎn)密任，此時(shí)我們開(kāi)始回溯。
【參考答案】
www.jiuzhang.com/solutions/construct-binary-tree-from-inorder-and-postorder-traversal/
