首先我們知道,前序遍歷的規(guī)則是：根結(jié)點(diǎn)→左子結(jié)點(diǎn)→右子結(jié)點(diǎn)
中序遍歷是：左子結(jié)點(diǎn)→根結(jié)點(diǎn)→右子結(jié)點(diǎn)
后序遍歷是：左子結(jié)點(diǎn)→右子結(jié)點(diǎn)→根結(jié)點(diǎn)
那么,對(duì)于一棵二叉樹,前序遍歷的第一個(gè)結(jié)點(diǎn)一定是這棵樹的根結(jié)點(diǎn),即根結(jié)點(diǎn)是a.
在中序遍歷的順序dgbaechf中,以a分成左、右兩邊,左邊是dgb,右邊是echf.
所以,這棵樹現(xiàn)在可以確定如下：
      a
     / \
dgb echf
接下來再分別對(duì)左子樹和右子樹進(jìn)行類似的操作.
對(duì)于左子樹dgb來說,在前序遍歷abdgcefh中找到bdg,證明這子樹的根是b,那么現(xiàn)在可以確定的樹結(jié)構(gòu)如下：
    a
   / \
  b  echf
 /
dg
再看dg,前序遍歷中的順序?yàn)閐g,所以d是dg這部分子樹的根,那么又因?yàn)橹行虮闅v的dg順序也是dg,所以g是右子結(jié)點(diǎn).
即：
    a
   / \
  b  echf
 /
d
 \
 g
現(xiàn)在看echf這部分子樹,前序中順序是cefh,所以子樹根結(jié)點(diǎn)是c,那么左子結(jié)點(diǎn)是e,右子樹是hf：
得到：
    a
   / \
  b  c
 /   / \
d  e hf
 \
 g
最后只剩下hf部分了,前序遍歷中是fh,所以根是f,那么h就是左子結(jié)點(diǎn).
現(xiàn)在得到了整棵樹：
    a
   / \
  b  c
 /   / \
d  e  f
 \    /
 g  h
對(duì)這棵樹再進(jìn)行后序遍歷就行了,結(jié)果就是：gdbehfca