借助栈

    public ArrayList<Integer> preorderTraversal (TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root; //当前节点
        while(cur!=null){
            list.add(cur.val); //遍历当前节点
            if(cur.right!=null)stack.add(cur.right); //右节点入栈
            cur = cur.left; //当前节点左移到左节点
            if(cur==null){//左节点为空
                if(stack.isEmpty())break; //cur为空，而且栈里面都空了，结束
                cur = stack.pop(); //否则就从栈里面弹出一个，cur指向它继续
            }
        }
        return list;
    }