morris中序遍历

morries遍历。 能将时间复杂度降低到2n,因为要遍历两次 O(n)

func morris(_ root:TreeNode?) {
        
        var node = root
        //直到节点是空的为止
        while node != nil {
          
            if node?.left != nil {
                //先找前驱节点(中序遍历的前一个节点)
                var pred = node?.left
                //因为会遍历两次，第二次的时候右边连着自己
                while pred?.right != nil && pred?.right !== node{
                    pred = pred?.right
                }
                //说明第一次找到前驱节点
                if pred?.right == nil {
                    pred?.right = node
                    node = node?.left
                }
                //说明是第二次，指向了自己 pred.right === node
                else{
                    print(node?.val as Any)
                    pred?.right = nil
                    node = node?.right
                }
                
                
                
            }
            //访问对应节点
            else{
                print(node?.val as Any)
                node = node?.right
            }
            
            
            
        }
        
    }