94. 二叉树的中序遍历
#leetcode#树#中序遍历#递归栈#非递归#栈模拟递归栈#线索化 2025-01-27

Problem: 94. 二叉树的中序遍历

思路

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

复杂度

  • 时间复杂度: $O(n)$
  • 空间复杂度: $O(1)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//! 利用线索树的思维，空指针不用白不用，写代码时记得画图，这样就能顺利敲出代码了 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;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//! 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;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//! 简单地用栈模拟函数栈的非递归写法 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;
  }
};