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 - 博客园
No comments:
Post a Comment