题目
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]示例 2：
输入：root = []
输出：[]示例 3：
输入：root = [1]
输出：[1]提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解答
- 递归算法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res){
//原函数没办法对vector数组的内容进行添加
if(!root) {
return;
}
//中 左 右
inorder(root->left, res);
res.push_back(root -> val);
inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
inorder(root, result);
return result;
}
};- 迭代
方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同，具体实现可以看下面的代码。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root != nullptr || !stk.empty()) {
//结点非空时，将root结点push进去， root迭代至左结点
while(root != nullptr) {
stk.push(root);
root = root -> left;
}
//符合条件的结点都push进去之后，出栈，然后将root结点的值push进res数组中，
root = stk.top();
stk.pop();
res.push_back(root -> val);
// 将root结点迭代至右结点
root = root -> right;
}
return res;
}
};- Morris遍历算法
思路与算法
Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 $O(1)$。
Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 $x$）：
如果 $x$ 无左孩子，先将 $x$ 的值加入答案数组，再访问 $x$ 的右孩子，即 $x = x.right $。
如果 $x$ 有左孩子，则找到 $x$ 左子树上最右的节点（即左子树中序遍历的最后一个节点，$x$ 在中序遍历中的前驱节点），我们记为 $predecessor $。根据 $predecessor $ 的右孩子是否为空，进行如下操作。
如果 $predecessor $ 的右孩子为空，则将其右孩子指向 $x$，然后访问 $x$ 的左孩子，即 $x = x.left $。
如果 $predecessor $ 的右孩子不为空，则此时其右孩子指向 $x$，说明我们已经遍历完 $x$ 的左子树，我们将 $predecessor $ 的右孩子置空，将 $x$ 的值加入答案数组，然后访问 $x$ 的右孩子，即 $x = x.right $。
重复上述操作，直至访问完整棵树。
其实整个过程我们就多做一步：假设当前遍历到的节点为 xxx，将 xxx 的左子树中最右边的节点的右孩子指向 xxx，这样在左子树遍历完成后我们通过这个指向走回了 xxx，且能通过这个指向知晓我们已经遍历完成了左子树，而不用再通过栈来维护，省去了栈的空间复杂度。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode *predecessor = nullptr;
while (root != nullptr) {
if(root -> left != nullptr) {
//predecessor就是当前root节点向左走一步，再一直向右走到无法走为止
predecessor = root -> left;
while(predecessor -> right != nullptr && predecessor -> right != root) {
predecessor = predecessor -> right;
}
//让predecessor的右指针指向root，继续遍历左子树
if (predecessor -> right == nullptr) {
predecessor -> right = root;
root = root -> left;
}
//说明左子树已经访问完了， 需要断开连接
else {
res.push_back(root -> val);
predecessor -> right = nullptr;
root = root -> right;
}
}
//如果没有左孩子，则直接访问右孩子
else {
res.push_back(root -> val);
root = root -> right;
}
}
return res;
}
};