public static ArrayList<Integer> preorderTraversal(TreeNode root) {
		// write your code here
		TreeNode c=root;
		ArrayList<Integer>rel=new ArrayList<>();
		while (c!=null) {
			if (c.left!=null) {
				TreeNode t=c.left;
				while (t.right!=null&&t.right!=c)
					t=t.right;
				if (t.right==null) {
					rel.add(c.val);
					t.right=c;
					c=c.left;
				} else {
					t.right=null;
					c=c.right;
				}
			} else {
				rel.add(c.val);
				c=c.right;
			}
		}
		return rel;
	}