二叉树中序遍历的递归与迭代实现

题目描述

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

示例 1：

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

输出：[1,3,2]

示例 2：

输入：root = []

输出：[]

示例 3：

输入：root = [1]

输出：[1]

---

用'第一性原理'（First Principles Thinking）来解决问题，意味着我们要剥离所有表象和经验主义的惯性，回归到事物最基本的真理，并从那里开始重新推导。

对于'二叉树中序遍历'，我们不直接去背诵代码，而是从最底层的物理逻辑开始。

回归本质——什么是二叉树和中序遍历？

1. 物理结构的基本事实：

一个二叉树节点（Node）只有三种状态或组成部分：

• 它自己（根/Root）
• 它的左边（左子树/Left）
• 它的右边（右子树/Right）

2. 任务的基本事实：

'遍历'意味着我们要走遍每一个节点，且不重不漏。

'中序'（In-order）是一个人为定义的顺序约定：左子树 -> 根节点 -> 右子树。

3. 推导：

无论这棵树多大，它在任何一个局部都必须遵循这个顺序。如果一个节点有左子树，你必须先处理完左边的一切，才能处理自己，最后处理右边。

---

寻找最简单的解法

如果我们从第一性原理出发，既然二叉树的定义本身就是递归的（一个节点又是另一棵树的根），那么最自然的解法就是递归。

逻辑推导：

1. 基本情况（Base Case）： 如果节点是空的，我什么都不用做，直接返回。
2. 原子操作：
   • 去处理左边：inorder(root->left)
   • 处理我自己（存入结果）：res.push_back(root->val)
   • 去处理右边：inorder(root->right)

C++ 代码实现（递归版）：

class Solution {
public:
    void traverse(TreeNode* root, vector<int>& res) {
        if (!root) return; // 基本事实：空节点无需处理
        traverse(root->left, res); // 先解决左边
        res.(root->val); 
        (root->right, res); 
    }
    
    {
        vector<> res;
        (root, res);
         res;
    }
};