HHot 100C++ 图解

94. 二叉树的中序遍历

简单 二叉树 4 帧动画 在力扣上做

一句话套路迭代栈 / Morris;递归就是左根右

题目描述

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

 

示例 1:

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

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

 

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

 

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

思路

时间O(n)
空间O(h)

迭代模板

一路向左压栈 -> 弹出访问 -> 转向右子树。

这个模板稍加改造就是 Q98 验证 BST、Q230 第 K 小、Q173 迭代器。

Morris 遍历

利用「前驱结点的右指针为空」临时建线索,可做到 O(1) 空间。

图解

1 3 2
二叉树(来自本仓库测试数据,nullopt 表示空位)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/08_binary_tree.cpp28 行
namespace lc0094 {
class Solution {
 public:
  static vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
      while (cur) {  // 一路向左
        st.push(cur);
        cur = cur->left;
      }
      cur = st.top();
      st.pop();
      ans.push_back(cur->val);  // 左根右:弹出时就是「根」
      cur = cur->right;
    }
    return ans;
  }

  static void inorderRec(TreeNode* root, vector<int>& out) {
    if (!root) return;
    inorderRec(root->left, out);
    out.push_back(root->val);
    inorderRec(root->right, out);
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q94_inorder_traversal11 行
lc0094::Solution s;
TreeNode* a = buildTree({1, nullopt, 2, 3});  // 3 是 2 的左孩子(层序序列化规则)
CHECK_EQ(s.inorderTraversal(a), vector<int>{1, 3, 2});  // 官方示例输出就是 [1,3,2]
vector<int> rec;
s.inorderRec(a, rec);
CHECK_EQ(rec, vector<int>{1, 3, 2});  // 递归版与迭代版结果必须一致
freeTree(a);
CHECK_EQ(s.inorderTraversal(nullptr), vector<int>{});
TreeNode* b = buildTree({2, 1, 3});
CHECK_EQ(s.inorderTraversal(b), vector<int>{1, 2, 3});
freeTree(b);

↑↓ 选择↵ 打开/ 随时唤起