Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively?
二叉樹的中序周遊順序為左-根-右，可以有遞歸和非遞歸來解，其中非遞歸解法又分為兩種，一種是使用棧來接，另一種不需要使用棧。我們先來看遞歸方法，十分直接，對左子結點調用遞歸函數，根節點通路值，右子節點再調用遞歸函數，代碼如下：
解法一：
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> res;
inorder(root, res);
return res;
}
void inorder(TreeNode *root, vector<int> &res) {
if (!root) return;
if (root->left) inorder(root->left, res);
res.push_back(root->val);
if (root->right) inorder(root->right, res);
}
}; 下面再來看非遞歸使用棧的解法，也是符合本題要求使用的解法之一，需要用棧來做，思路是從根節點開始，先将根節點壓入棧，然後再将其所有左子結點壓入棧，然後取出棧頂節點，儲存節點值，再将目前指針移到其右子節點上，若存在右子節點，則在下次循環時又可将其所有左子結點壓入棧中。這樣就保證了通路順序為左-根-右，代碼如下：
解法二：
// Non-recursion
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (p || !s.empty()) {
while (p) {
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
res.push_back(p->val);
p = p->right;
}
return res;
}
}; 下面這種解法跟 Binary Tree Preorder Traversal 中的解法二幾乎一樣，就是把結點值加入結果 res 的步驟從 if 中移動到了 else 中，因為中序周遊的順序是左-根-右，參見代碼如下：
解法三：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
TreeNode *p = root;
while (!s.empty() || p) {
if (p) {
s.push(p);
p = p->left;
} else {
p = s.top(); s.pop();
res.push_back(p->val);
p = p->right;
}
}
return res;
}
}; 下面來看另一種很巧妙的解法，這種方法不需要使用棧，是以空間複雜度為常量，這種非遞歸不用棧的周遊方法有個專門的名字，叫 Morris Traversal，在介紹這種方法之前，先來引入一種新型樹，叫 Threaded binary tree，這個還不太好翻譯，第一眼看上去以為是叫線程二叉樹，但是感覺好像又跟線程沒啥關系，後來看到網上有人翻譯為螺紋二叉樹，但部落客認為這翻譯也不太敢直視，很容易讓人聯想到為計劃生育做出突出貢獻的某世界著名品牌，後經熱心網友提醒，應該叫做線索二叉樹。先來看看維基百科上關于它的英文定義：
A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.
就是說線索二叉樹實際上是把所有原本為空的右子節點指向了中序周遊順序之後的那個節點，把所有原本為空的左子節點都指向了中序周遊之前的那個節點，具體例子可以點選這裡。那麼這道題跟這個線索二叉樹又有啥關系呢？由于既不能用遞歸，又不能用棧，那如何保證通路順序是中序周遊的左-根-右呢。原來需要建構一個線索二叉樹，需要将所有為空的右子節點指向中序周遊的下一個節點，這樣中序周遊完左子結點後，就能順利的回到其根節點繼續周遊了。具體算法如下：
1. 初始化指針 cur 指向 root
2. 當 cur 不為空時
- 如果 cur 沒有左子結點
a) 列印出 cur 的值
b) 将 cur 指針指向其右子節點
- 反之
将 pre 指針指向 cur 的左子樹中的最右子節點
* 若 pre 不存在右子節點
a) 将其右子節點指回 cur
b) cur 指向其左子節點
* 反之
a) 将 pre 的右子節點置空
b) 列印 cur 的值
c) 将 cur 指針指向其右子節點
解法四：
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> res;
if (!root) return res;
TreeNode *cur, *pre;
cur = root;
while (cur) {
if (!cur->left) {
res.push_back(cur->val);
cur = cur->right;
} else {
pre = cur->left;
while (pre->right && pre->right != cur) pre = pre->right;
if (!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = NULL;
res.push_back(cur->val);
cur = cur->right;
}
}
}
return res;
}
}; 其實 Morris 周遊不僅僅對中序周遊有用，對先序和後序同樣有用，具體可參見網友 NOALGO 部落格，和 Annie Kim's Blog 的部落格。是以對二叉樹的三種常見周遊順序(先序，中序，後序)就有三種解法(遞歸，非遞歸，Morris 周遊)，總共有九段代碼呀，熟練掌握這九種寫法才算初步掌握了樹的周遊挖~~ 至于二叉樹的層序周遊也有遞歸和非遞歸解法，至于有沒有 Morris 周遊的解法還有待大神們的解答，若真有也請勞煩告知部落客一聲~~
Github 同步位址：
https://github.com/grandyang/leetcode/issues/94
類似題目：
Validate Binary Search Tree
Binary Tree Preorder Traversal
Binary Tree Postorder Traversal
Binary Search Tree Iterator
Kth Smallest Element in a BST
Closest Binary Search Tree Value II
Inorder Successor in BST
參考資料：
https://leetcode.com/problems/binary-tree-inorder-traversal/
https://leetcode.com/problems/binary-tree-inorder-traversal/discuss/31231/c-ierative-recursive-and-morris-traversal
https://leetcode.com/problems/binary-tree-inorder-traversal/discuss/31213/iterative-solution-in-java-simple-and-readable
https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45551/preorder-inorder-and-postorder-iteratively-summarization
https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/45621/preorder-inorder-and-postorder-traversal-iterative-java-solution
LeetCode All in One 題目講解彙總(持續更新中...)
喜歡請點贊，疼愛請打賞❤️~.~ 微信打賞  | Venmo 打賞 |