特点

利用已经存在的二叉树right指针遍历，从而达到空间复杂度只有O(1)

算法描述

  1. 初始化当前节点为根节点
  2. 若当前节点为空，则遍历完毕，否则进入3
  3. 若当前节点的左节点为空，则访问当前节点，并更新当前节点的右节点为当前节点，并进入2，否则进入4
  4. 此时当前节点的左节点不为空，寻找当前节点在左子树中的中序前驱节点，如果中序前序节点的right指针为空，进入5，如果right指针等于当前节点，进入6
  5. 前驱节点的right指针为空，表明第一次访问到当前节点，则访问当前节点，令前驱节点的right指针指向当前节点，以便访问完前驱节点后可以回溯到当前节点，最后更新当前节点的左节点为当前节点，进入2。
  6. 此时前驱节点的right指针等于当前节点，表明是第二次访问到当前节点，首先还原right指针为空，并且直接更新当前节点的右节点为当前节点，进入2。

算法实现

  1. public class Solution144_version3 {
  2.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         //Morris迭代遍历，最重要的是利用已经存在的right指针
  4.         List<Integer> res = new LinkedList<>();
  5.         //两个辅助指针
  6.         TreeNode p1 = root; //代表当前节点
  7.         TreeNode p2 = null;
  8.         while(p1 != null){
  9.             p2 = p1.left;
  10.             //当前节点的左节点不为空则寻找当前节点在左子树中的中序前驱节点
  11.             if(p2 != null){
  12.                 //寻找前驱节点
  13.                 while(p2.right != null && p2.right != p1){
  14.                     p2 = p2.right;
  15.                 }
  16.                 //此时要么p2.right == null 要么p2.right == p1
  17.                 if(p2.right == null){
  18.                     //此时表明第一次访问到当前节点，可以直接访问当前节点
  19.                     res.add(p1.val);
  20.                     //并将前驱节点指向当前节点
  21.                     p2.right = p1;
  22.                     //更新当前节点为当前节点的左节点
  23.                     p1 = p1.left;
  24.                     continue;
  25.                 }else{
  26.                     //此时p2.right == p1，表明第二次访问到当前节点，应该去访问当前节点的右节点，
  27.                     //并还原指针
  28.                     p2.right = null;
  29.                     p1 = p1.right;
  30.                 }
  31.             }else{
  32.                 //当前节点的左节点为空时，也应当先访问当前节点，在更新当前节点为当前节点的右节点
  33.                 res.add(p1.val);
  34.                 p1 = p1.right;
  35.             }
  36.         }
  37.         return res;
  38.     }
  39. }