Java solution -- preorder Morris traversal
![preorder Morris traversal][1]\n\n    public List preorderTraversal(TreeNode node) {\n        List list = new ArrayList();\n        \n        while(node != nul
![preorder Morris traversal][1]\n\n    public List<Integer> preorderTraversal(TreeNode node) {\n        List<Integer> list = new ArrayList();\n        \n        while(node != null) {\n            if(node.left == null) {\n                list.add(node.val);\n                node = node.right;\n            }\n            else {\n                TreeNode nextNode = node.left;\n                \n                TreeNode p = nextNode;\n                while(p.right != null) p = p.right;\n                \n                list.add(node.val);\n                p.right = node.right;\n                node = nextNode;\n            }\n        }\n        return list;\n    }\n\n\n  [1]: http://images.cnitblog.com/blog/300640/201306/14221458-aa5f9e92cce743ccacbc735048133058.jpg
[]