中序遍歷定義：
先訪問 left subtree，再訪問curNode，再訪問right subtree
思路：
根據(jù)中序遍歷的定義，利用stack來實(shí)現(xiàn)
1. 找到先要訪問的left most node
2. 訪問
3. 如果有right subtree，利用同樣的方法夏醉，再進(jìn)行訪問
4. 如果沒有right subtree，說明當(dāng)前curNode已經(jīng)被fully visited
5. 重復(fù)直到所有節(jié)點(diǎn)被訪問
關(guān)鍵：
- stack的意義是涌韩？
既然stack的方法可以替代recursion的方法畔柔，那么stack一定實(shí)現(xiàn)了recursion中的某個(gè)功能。什么功能呢臣樱？backtrack靶擦！
試想一下，當(dāng)訪問完左子樹之后需要父節(jié)點(diǎn)擎淤，那么怎么才能夠從左子樹的最后一個(gè)被訪問節(jié)點(diǎn)跳到父節(jié)點(diǎn)奢啥？
利用Stack秸仙，可以先將父節(jié)點(diǎn)壓到棧底嘴拢，當(dāng)左子樹的節(jié)點(diǎn)被完全訪問之后，說明棧中已無(wú)左子樹的節(jié)點(diǎn)寂纪，棧頂節(jié)點(diǎn)即為父節(jié)點(diǎn)席吴。
因此，stack中節(jié)點(diǎn)的的意義是：
- 棧頂的節(jié)點(diǎn)是下一個(gè)要訪問的節(jié)點(diǎn)
- 位于頂端的比位于底端的節(jié)點(diǎn)先得到訪問
- 已訪問的節(jié)點(diǎn)已出棧
- 后訪問的節(jié)點(diǎn)可能在棧中或者還未被加到棧中
- 如何“重復(fù)直到所有節(jié)點(diǎn)被訪問”捞蛋？
既然知道了stack的意義孝冒，那么當(dāng)stack為空，則表示所有節(jié)點(diǎn)被訪問拟杉。
while (!stack.empty()) {
...
}
- 如何“找到left most node”并同時(shí)將父節(jié)點(diǎn)壓到棧中庄涡？
while (cur.left != null) {
stack.push(cur.left);
cur = cur.left;
}
//add leftmost
cur = stack.pop();
rst.add(cur.val);
- 如果有right subtree？
// right subtree if possible
if (cur.right != null) {
stack.push(cur.right);
}
- 如果沒有right subtree搬设？
說明棧頂node的left subtree已經(jīng)被fully visited穴店，此時(shí)棧頂節(jié)點(diǎn)則為下一個(gè)要訪問的點(diǎn)撕捍，此時(shí)可以直接回到while的起始重復(fù)執(zhí)行。
但是有一個(gè)問題泣洞，當(dāng)回到棧頂?shù)墓?jié)點(diǎn)時(shí)忧风，又要經(jīng)過3的循環(huán)，即有可能重復(fù)訪問已經(jīng)訪問過的left subtree
解決方法是：
- 剪枝cut branch
因?yàn)楫?dāng)發(fā)現(xiàn)沒有right subtree時(shí)球凰，說明棧頂node的left subtree已經(jīng)被fully visited狮腿，因此可以將其left設(shè)置為null。
// right subtree if possible
if (cur.right != null) {
stack.push(cur.right);
} else if (!stack.empty()) { //cur subtree is fully visited
stack.peek().left = null; //cut cur subtree
}
但改方法更改了輸入呕诉，不好缘厢。
- 既然查是否visited嘛，利用個(gè)set唄
while (cur.left != null && !visited.contains(cur.left)) {
stack.push(cur.left);
cur = cur.left;
}
//add leftmost
cur = stack.pop();
rst.add(cur.val);
visited.add(cur);
- 巧妙利用在最后使curNode = curNode.right + 找leftmost之前判斷一下curNode是否為null甩挫，將判斷當(dāng)前subtree是否被fully visited的任務(wù)放到找leftmost之前昧绣。
while (!stack.empty()) {
if (cur != null) { //when curNode == null, it means cur subtree is fully visited
// push into stack until the leftmost
while (cur.left != null) {
stack.push(cur.left);
cur = cur.left;
}
}
//add leftmost
cur = stack.pop();
rst.add(cur.val);
// right subtree if possible
if (cur.right != null) {
stack.push(cur.right);
}
cur = cur.right;
}
return rst;
}
