# Morris 遍歷二元樹
- [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)
- [144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)
- [145. Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal/)
## In order
- 左樹為空，則輸出當前節點，跳至右樹
- 左樹非空，先找到`前驅節點`
- (1) 右樹為空: 未處理完左樹，設定暫時連結
- (2) 右樹非空: 已處理完左樹，回復暫時連結，輸出，跳至右樹

    vector<int> morris(TreeNode *root){
        if(!root)   return {};
        vector<int> ans;
        while(root!=NULL){
            if(root->left==NULL){
                ans.push_back(root->val);
                root = root->right;
            }else{
                TreeNode *tmp = root->left;
                while(tmp->right && tmp->right!=root)   tmp = tmp->right;
                if(tmp->right==NULL){
                    tmp->right = root;
                    root = root->left;
                }else{
                    tmp->right = NULL;
                    ans.push_back(root->val);
                    root = root->right;
                }
            }
        }
        return ans;
    }