二叉树后序遍历之Morris遍历：

特点

  • 时间复杂度：O(n)，但左子树节点会被访问3次
  • 空间复杂度：O(1)，会利用已经存在的right指针，并且在访问完毕后将这些空的right指针还原

算法流

  1. 初始化：令当前节点为root，
  2. 若当前节点为空，结束遍历，若当前遍历不为空，则进入3
  3. 寻找当前节点在中序遍历下的前驱节点，即：当前节点的左子树中最右节点，进入4
  4. 若该前驱节点的right指针为空，则令其指向当前节点，并令更新当前节点的左节点为当前节点，否则进入5
  5. 此时前驱节点的right指针因为4中修改，必指向当前节点，此时首先还原right指针为null，并将从当前节点的左子树到前驱节点这条路径上的节点逆序输入到结果集中。
  6. 重复2，3，4
  7. 当从2节点遍历后，将从根节点到最右节点这条路径上节点逆序输出至结果集中。

算法代码

  1. public class Solution145_version3 {
  2.     public List<Integer> postorderTraversal(TreeNode root) {
  3.         List<Integer> res = new LinkedList<>();
  4.         //两个辅助指针
  5.         TreeNode p1 = root; //表示当前节点
  6.         TreeNode p2 = null; //表示当前节点的左节点
  7.         while(p1 != null){//当前节点为空，表示遍历完毕
  8.             p2 = p1.left;
  9.             //当前节点存在左子树时，去寻找当前节点在中序遍历下的前驱节点，
  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.                     p2.right = p1;
  20.                     //继续向左下访问
  21.                     p1 = p1.left;
  22.                     continue;
  23.                 }else{//p2.right == p1，
  24.                     //此时应当还原指针
  25.                     p2.right = null;
  26.                     // 表明第二次访问到当前节点，逆序输出从当前节点的左节点到前驱节点的序列
  27.                     res.addAll(addPath(p1.left));
  28.                 }
  29.             }
  30.             p1 = p1.right;
  31.         }
  32.         //最终循环结束，从root节点开始的最右路径没有访问
  33.         res.addAll(addPath(root));
  34.         return res;
  35.     }
  37.     //逆序输出从指定节点到最右子节点的序列
  38.     List<Integer> addPath(TreeNode node){
  39.         LinkedList<Integer> res = new LinkedList<>();
  40.         while(node != null){
  41.             res.addFirst(node.val);
  42.             node = node.right;
  43.         }
  44.         return res;
  45.     }
  46. }