中序遍历二叉树+O(1)空间

问题描述

中序遍历二叉树时，很简单，需要加上递归就可以优雅地实现了。当然，使用递归的话，函数调用栈的空间就会达到O(log n)。那么有什么方式，可以使得中序遍历二叉树的复杂度为O(1)呢？

问题分析

既然要保证O(1)复杂度，那么就不能使用递归调用了。目标方案应该是使用while或for循环的方式。下面借用一张图来解释（来源：）：

如图所示，需要在多个节点（right指针为空），，设置指针指向父节点。这样在遍历的时候，就可以依靠这个指针来返回父节点了。在遍历完后，这些辅助指针会被撤去。

解决方案

这里直接用代码表示出来：

class TreeNode {public:int val;TreeNode *left, *right;TreeNode(int val) {this->val = val;this->left = this->right = NULL;}}; void inorderConstSpace(TreeNode *root) {while (root != NULL) {) {printf(“%d\n”, root->val);root = root->right;continue;}// find preceding nodeTreeNode *pre = NULL;for (pre = root->left; pre->right != root && pre->right != NULL;pre = pre->right) {}) {pre->right = root;root = root->left;} else {// preceding node is visited for the second timeprintf(“%d\n”, root->val);root = root->right;pre->right == NULL;}}}

如果你希望成功，以恒心为良友，以经验为参谋，以小心为兄弟，以希望为哨兵。