题目

给定一个二叉树的根节点 root，返回 它的 中序 遍历 。

示例 1：
屏幕截图 2022-05-31 001824.jpg

  1. 输入：root = [1,null,2,3]
  2. 输出：[1,3,2]

示例 2：

  1. 输入：root = []
  2. 输出：[]

示例 3：

  1. 输入：root = [1]
  2. 输出：[1]

提示：

  • 树中节点数目在范围 [0, 100] 内

  • -100 <= Node.val <= 100


    进阶: 递归算法很简单，你可以通过迭代算法完成吗？

    解题方法

    递归

    通过递归调用的方式先后处理左子树、父节点、右子树。
    时间复杂度O(n)，空间复杂度O(logn)，最劣O(n)
    C++代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   void mid_order(TreeNode* p, vector<int>& vec) {
    15.       if(p!=NULL) {
    16.           if(p->left != NULL)     mid_order(p->left, vec);
    17.           vec.push_back(p->val);
    18.           if(p->right != NULL)    mid_order(p->right, vec);
    19.       }
    20.   }
    22.   vector<int> inorderTraversal(TreeNode* root) {
    23.       vector<int> result;
    24.       if(root == NULL)    return result;
    26.       mid_order(root, result);
    28.       return result;
    29.   }
    30. };

    迭代

    使用 栈 记录节点，通过指针前往最左子树，当指针指向节点的左节点为空时，再依次将指针所在节点压入数组，并前往右子树，并继续前往最左子树，重复上述操作。
    时间复杂度O(n)，空间复杂度O(logn)，最劣O(n)
    C++代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   void mid_order(TreeNode* p, vector<int>& vec) {
    15.       stack<TreeNode*> nodes;
    16.       TreeNode* cur = p;
    17.       while(cur != NULL || nodes.size()>0) {
    18.           if(cur!=NULL) {
    19.               nodes.push(cur);
    20.               cur = cur->left;
    21.           }         
    22.           else {
    23.               cur = nodes.top();
    24.               nodes.pop();
    25.               vec.push_back(cur->val);    // 父节点
    26.               cur = cur->right;            // 右子树
    27.           }
    28.       }
    29.   }
    31.   vector<int> inorderTraversal(TreeNode* root) {
    32.       vector<int> result;
    33.       if(root == NULL)    return result;
    35.       mid_order(root, result);
    37.       return result;
    38.   }
    39. };

    Morris 遍历

    使用 Morris 遍历，在完成左子树后返回父节点，即当前节点左子树的最右节点的右节点指向当前节点，将父节点压入数组，再处理右子树。当前节点左子树为空时，将当前节点压入数组，并处理右节点。
    时间复杂度O(n)，空间复杂度O(1)
    C++代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   vector<int> inorderTraversal(TreeNode* root) {
    15.       vector<int> result;
    16.       TreeNode *mostright, *cur=root;
    17.       if(root == NULL)    return result;
    19.       while(cur!=NULL) {
    20.           mostright = cur->left;
    21.           if(mostright!=NULL) {
    22.               while(mostright->right != NULL && mostright->right != cur)     mostright = mostright->right;
    24.               if(mostright->right == NULL) {
    25.                   mostright->right = cur;
    26.                   cur = cur->left;
    27.               }
    28.               else {
    29.                   mostright->right = nullptr;
    30.                   result.push_back(cur->val);        // 父节点
    31.                   cur = cur->right;                // 右子树
    32.               }
    33.           }
    34.           else {
    35.               result.push_back(cur->val);
    36.               cur = cur->right;
    37.           }
    38.       }
    40.       return result;
    41.   }
    42. };

    标记法（二叉树遍历的统一写法）

    设置标志位来判别节点是否二次访问，对二次访问的节点压入数组。
    时间复杂度O(n)，空间复杂度O(logn)，最劣O(n)
    C++代码：

    /**
* 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> result;
      stack<TreeNode*> nodes;
      if(root != nullptr)     nodes.push(root);

      while(nodes.size()>0) {
          TreeNode *tmp = nodes.top();
          if(tmp != NULL) {
              nodes.pop();
              if(tmp->right != nullptr)   nodes.push(tmp->right);
              nodes.push(tmp);
              nodes.push(NULL);
              if(tmp->left != nullptr)    nodes.push(tmp->left);
          }
          else {
              nodes.pop();
              tmp = nodes.top();
              result.push_back(tmp->val);
              nodes.pop();
          }
      }

      return result;
  }
};