題目的大意是說,給你一棵 binary tree 的 preorder 和 inorder traversal
要你寫出它的 postorder traversal
preorder : root ---> left subtree ---> right subtree
inorder : letf subtree ---> root ---> right subtree
postorder: left subtree ---> right subtree ---> root
我是用 Recursive Method 來完成
現在用 A 代表 root ; B 代表 left subtree ; C 代表 right subtree
=> preorder ---> A***** ******* (A is only one component)
^^^^^ ^^^^^^^
B C
=> inorder ---> *****A *******
^^^^^ ^^^^^^^
B C
=> postorder ---> output(B) ; output(C) ; output(A)
因為 A 集合中只有一個元素所以直接印出來就可以啦
而 B 和 C 集合中不一定只有一個元素,所以把 B 和 C 當作一棵樹
用同樣的方法去分解
=> output(B) ---> output(B.B) ; output(B.C) ; output(B.A)
做到都只剩一個元素時就已經完成
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.249.215