Morris Traversal 模板

解决问题 用O（1）的空间来访问所有的BST 上的点 结合Inorder 就可以输出从小到大的排序顺序

模板代码如下

1. 
   
2. class Solution {
   
3.     public void recoverTree(TreeNode root) {
   
4.         while(root != null){
   
5.             if(root.left != null){
   
6.                 TreeNode temp = root.left;
   
7.                 //目地是走到该左子树最右边的node
   
8.                 while(temp.right != null && temp.right != root){
   
9.                     temp = temp.right;
   
10.                 }
    
11.                 //如果while循环条件中任意一个不满足
    
12.                 if(temp.right == null){
    
13.                     temp.right = root;
    
14.                     root = root.left;
    
15.                 } else {
    
16.                    //将该点断开
    
17.                     temp.right = null;
    
18.                     //visit root.val
    
19.                     root = root.right;
    
20.                 }
    
21.             } else {
    
22.                 //vsiite root.val
    
23.                 root = root.right;
    
24.             }
    
25.         }
    
26.     }
    
27. }
    

复制代码

文章来源
1. https://www.youtube.com/watch?v=QZMropFflv4          （模板来源）
2. https://www.youtube.com/watch?v=wGXB9OWhPTg   （具体分析）


补充内容 (2021-12-10 06:08 +8:00):
学这个模板的目的是为了解决第99题的。个人感觉recursion就可以了，但是视频里说是 jvm的stack 也算是额外空间，所以用他。我觉得他说的不对，因为你临时变量也是存在jvm的stack当中的，并没有节省空间。这个算法的唯一目的就是为了替代iteration。因为Iteration的解法，我们需要用到Stack（数据结构的stack）肯定是要用到额外的空间的。因此采用morris traversal 可以有效的将额外空间从 o(n)降低到 o(1）

要不要掌握 看你们自己吧。多学一点东西是没错的。但是你时间紧迫就抓紧联系recursion就好了。