解析

利用线索树的思维，用空闲的右指针保存访问顺序，使得空间复杂度为O(1)。
要记得及时还原指针，毕竟是外部的数据，尽量不修改。

线索化

利用线索树的思维，空指针不用白不用，写代码时记得画图，这样就能顺利敲出代码了

//!  n,1
class Solution {
 public:
  vector<int> inorderTraversal(TreeNode *root) {
    vector<int> res;
    TreeNode *node = root;
    TreeNode *predecessor = nullptr;
    while (node != nullptr) {
      if (node->left != nullptr) {
        predecessor = node->left;
        while (predecessor->right != nullptr && predecessor->right != node) {
          predecessor = predecessor->right;
        }
        if (predecessor->right != node) {
          predecessor->right = node;
          node = node->left;
        } else {
          predecessor->right = nullptr;
          res.push_back(node->val);
          node = node->right;
        }
      } else {
        res.push_back(node->val);
        node = node->right;
      }
    }
    return res;
  }
};

//! n,n -> 递归写法 n次节点遍历；递归栈深度log(n)~n，res存n个int
class Solution {
 public:
  vector<int> inorderTraversal(TreeNode *root) {
    vector<int> res;
    TreeNode *node = root;
    inOrder(root, res);
    return res;
  }
  void inOrder(TreeNode *node, vector<int> &res) {
    if (node == nullptr) {
      return;
    }
    inOrder(node->left, res);
    res.push_back(node->val);
    inOrder(node->right, res);
    return;
  }
};

//! 简单地用栈模拟函数栈的非递归写法 n,n
class Solution {
 public:
  vector<int> inorderTraversal(TreeNode *root) {
    vector<int> res;
    stack<TreeNode *> treeStack;
    TreeNode *node = root;
    while (node != nullptr || !treeStack.empty()) {
      while (node != nullptr) {
        treeStack.push(node);
        node = node->left;  // 一路存到最左下节点
      }
      node = treeStack.top();
      treeStack.pop();
      res.emplace_back(node->val);
      node = node->right;  // 从栈中取元素后看看有没有右子树
    }
    return res;
  }
};

2025-01-27 该篇文章被 HopoZ 打上标签: leetcode 树中序遍历递归栈非递归栈模拟递归栈线索化归为分类: algo