class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> inorder = new ArrayList<Integer>(); TreeNode cur = root; while(cur != null) { if(cur.left == null) { inorder.add(cur.val); cur = cur.right; } else { TreeNode prev = cur.left; while(prev.right != null && prev.right != cur) { prev = prev.right; } if(prev.right == null) { prev.right = cur; cur = cur.left; } else { prev.right = null; inorder.add(cur.val); cur = cur.right; } } } return inorder; } }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; 14 while (prev->right != NULL && prev->right != cur) 15 prev = prev->right; 16 17 if (prev->right == NULL) // 2.a) 18 { 19 prev->right = cur; 20 cur = cur->left; 21 } 22 else // 2.b) 23 { 24 prev->right = NULL; 25 printf("%d ", cur->val); 26 cur = cur->right; 27 } 28 } 29 } 30 }