Morris Traversal In Order, pre Order, Post Order
\n# Code\njava []\npublic class Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> preorder = new ArrayList<>();\n  
\n# Code\n```java []\npublic class Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> preorder = new ArrayList<>();\n        TreeNode cur = root;\n        \n        while (cur != null) {\n            if (cur.left == null) {\n                preorder.add(cur.val);\n                cur = cur.right;\n            } else {\n                TreeNode prev = cur.left;\n                while (prev.right != null && prev.right != cur) {\n                    prev = prev.right;\n                }\n                \n                if (prev.right == null) {\n                    prev.right = cur;\n                    preorder.add(cur.val); \n                    cur = cur.left;\n                } else {\n                    prev.right = null;\n                    cur = cur.right;\n                }\n            }\n        }\n        \n        return preorder;\n    }\n}\n\n```\n```java []\npublic class Solution {\n    public List<Integer> inorderTraversal(TreeNode root) {\n        List<Integer> inorder = new ArrayList<>();\n        TreeNode cur = root;\n\n        while (cur != null) {\n            if (cur.left == null) {\n                inorder.add(cur.val);\n                cur = cur.right;\n            } else {\n                TreeNode prev = cur.left;\n                while (prev.right != null && prev.right != cur) {\n                    prev = prev.right;\n                }\n\n                if (prev.right == null) {\n                    prev.right = cur;\n                    cur = cur.left;\n                } else {\n                    prev.right = null;\n                    inorder.add(cur.val);\n                    cur = cur.right;\n                }\n            }\n        }\n        return inorder;\n    }\n}\n```\n```java []\npublic class Solution {\n    public List<Integer> postorderTraversal(TreeNode root) {\n        List<Integer> postorder = new ArrayList<>();\n        TreeNode cur = root;\n        \n        while (cur != null) {\n            if (cur.right == null) {\n                postorder.add(cur.val);\n                cur = cur.left;\n            } else {\n                TreeNode pred = cur.right;\n                while (pred.left != null && pred.left != cur) {\n                    pred = pred.left;\n                }\n                \n                if (pred.left == null) {\n                    pred.left = cur;\n                    postorder.add(cur.val);\n                    cur = cur.right;\n                } else {\n                    pred.left = null;\n                    cur = cur.left;\n                }\n            }\n        }\n        \n        Collections.reverse(postorder);\n        return postorder;\n    }\n}\n\n```\n
['Tree', 'Java']