【題目描述】
Given a binary tree, return the inorder traversal of its nodes' values.
給出一棵二叉樹(shù),返回其中序遍歷
【題目鏈接】
www.lintcode.com/en/problem/binary-tree-inorder-traversal/
【題目解析】
遞歸版
最好理解，遞歸調(diào)用時(shí)注意返回值和遞歸左右子樹(shù)的順序即可。
迭代版
使用輔助棧，空間復(fù)雜度O(n),時(shí)間復(fù)雜度O(n).
中序遍歷沒(méi)有前序遍歷好寫，其中之一就在于入棧出棧的順序和限制規(guī)則。我們采用「左根右」的訪問(wèn)順序可知主要有如下四步構(gòu)成。
1.首先需要一直對(duì)左子樹(shù)迭代并將非空節(jié)點(diǎn)入棧
2.節(jié)點(diǎn)指針為空后不再入棧
3.當(dāng)前節(jié)點(diǎn)為空時(shí)進(jìn)行出棧操作，并訪問(wèn)棧頂節(jié)點(diǎn)
4.將當(dāng)前指針p用其右子節(jié)點(diǎn)替代
步驟2,3,4對(duì)應(yīng)「左根右」的遍歷結(jié)構(gòu)，只是此時(shí)的步驟2取的左值為空。
【參考答案】
