二叉树的中序遍历(三种方法详解)
- 题目描述
- 示例
- 提示
- 方法 1:递归法
- 思路
- 代码实现
- 复杂度分析
- 方法 2:迭代法(栈模拟)
- 思路
- 代码实现
- 复杂度分析
- 方法 3:Morris 遍历(线索化二叉树)
- 思路
- 代码实现
- 复杂度分析
- 三种方法对比
- 总结
题目描述
给定一个二叉树的根节点 root
,返回它的 中序遍历 结果。
示例
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
提示
- 树中节点数目在范围
[0, 100]
内 -100 <= Node.val <= 100
方法 1:递归法
思路
中序遍历的顺序为:左子树 → 根节点 → 右子树。
代码实现
#include <stdlib.h>struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};void inorder(struct TreeNode* root, int* result, int* returnSize) {if (!root) {return;}inorder(root->left, result, returnSize);result[(*returnSize)++] = root->val;inorder(root->right, result, returnSize);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {int* result = (int*)malloc(501 * sizeof(int)); // 预分配足够的空间*returnSize = 0;inorder(root, result, returnSize);return result;
}
复杂度分析
- 时间复杂度:O(n),每个节点访问一次。
- 空间复杂度:O(n),最坏情况下(单链表形式的树),递归调用栈深度为 O(n)。
方法 2:迭代法(栈模拟)
思路
使用栈来模拟递归过程:
- 先沿着左子树一路入栈,直到最左叶子。
- 弹出栈顶元素,访问该节点。
- 转向右子树,继续步骤 1 和 2。
代码实现
#include <stdlib.h>int* inorderTraversal(struct TreeNode* root, int* returnSize) {int* result = (int*)malloc(501 * sizeof(int));*returnSize = 0;struct TreeNode** stack = (struct TreeNode**)malloc(501 * sizeof(struct TreeNode*));int top = 0;while (root || top) {while (root) {stack[top++] = root;root = root->left;}root = stack[--top]; // 出栈访问result[(*returnSize)++] = root->val;root = root->right;}free(stack);return result;
}
复杂度分析
- 时间复杂度:O(n),每个节点入栈和出栈各一次。
- 空间复杂度:O(n),最坏情况下栈深度为 O(n)。
方法 3:Morris 遍历(线索化二叉树)
思路
Morris 遍历通过线索二叉树来减少空间复杂度,步骤如下:
- 如果当前节点没有左子树,访问该节点并进入右子树。
- 如果当前节点有左子树,找到前驱节点(左子树的最右节点):
- 若前驱节点的
right
为空,将其right
指向当前节点,然后进入左子树。 - 若前驱节点的
right
为当前节点,说明左子树已访问,访问当前节点,恢复前驱节点的right
指针为空,然后进入右子树。
- 若前驱节点的
代码实现
#include <stdlib.h>int* inorderTraversal(struct TreeNode* root, int* returnSize) {int* result = (int*)malloc(501 * sizeof(int));*returnSize = 0;struct TreeNode* predecessor = NULL;while (root) {if (root->left) {predecessor = root->left;while (predecessor->right && predecessor->right != root) {predecessor = predecessor->right;}if (!predecessor->right) {predecessor->right = root;root = root->left;} else {result[(*returnSize)++] = root->val;predecessor->right = NULL;root = root->right;}} else {result[(*returnSize)++] = root->val;root = root->right;}}return result;
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/binary-tree-inorder-traversal/solutions/412886/er-cha-shu-de-zhong-xu-bian-li-by-leetcode-solutio/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
复杂度分析
- 时间复杂度:O(n),每个节点访问最多两次。
- 空间复杂度:O(1),仅使用了额外的指针变量。
三种方法对比
方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
---|---|---|---|
递归 | O(n) | O(n) | 代码简洁,适合初学者 |
迭代(栈) | O(n) | O(n) | 适用于系统栈深度受限的情况 |
Morris | O(n) | O(1) | 适用于对空间复杂度有严格要求的情况 |
总结
- 递归法 是最直观的方法,但会消耗额外的栈空间。
- 迭代法(栈模拟) 通过显式栈实现递归过程,适用于深度受限的情况。
- Morris 遍历法 通过修改树结构实现 O(1) 空间复杂度,是一种高效方法,但对原树结构有一定影响。