Morris Traversal方法可以做到这两点,与前两种方法的不同在于该方法只需要O(1)空间,而且同样可以在O(n)时间内完成。 Morris只提供了中序遍历的方法,在中序遍历的基础上稍加修改可以实现前序,而后续就要再费点心思了。所以先从中序开始介绍。 首先定义在这篇文章中使用的二叉树节点结构,即由val,left和right组成: 1 struct TreeNode { 2 int val; 3 TreeNode *left; 4 TreeNode *right; 5 TreeNode(int x) : val(x), left(NULL), right(NULL) {} 6 }; 一、中序遍历 3. 重复以上1、2直到当前节点为空。 代码: 1 void inorderMorrisTraversal(TreeNode *root) { 2 TreeNode *cur = root, *prev = NULL; 3 while (cur != NULL) 4 { 5 if (cur->left == NULL) // 1. 6 { 7 printf("%d ", cur->val); 8 cur = cur->right; 9 } 10 else 11 { 12 // find predecessor 13 prev = cur->left;
Read full article from Morris Traversal方法遍历二叉树(非递归,不用栈,O(1)空间) - AnnieKim - 博客园