描述

给定一个大小为 n*m 的矩阵，请以对角线遍历并返回遍历结果
数据范围：  ，矩阵中的元素满足 
例1、输入：[[1,2,3],[4,5,6],[7,8,9]]，输出： [1,2,4,7,5,3,6,8,9]
例2、输入：[[1,3],[2,4]]，输出：[1,3,2,4]
问题分析：通过观察发现所有(i+j)为奇数的点都是斜向下（除了结尾的点），所有(i+j)为偶数的点（除了开始点）都是斜向上。
奇数点的尾部只要i<m，直接++i，否则++j。而偶数点的开头只要j<n,直接++j，否则++i。
当i=m&&j=n时退出循环。
下面给一个例子：

很直观的可以发现所有奇数点都是斜向下的，而所有偶数点都是斜向上的。（）里面表示坐标，
括号外面的数字表示遍历顺序。
复杂度分析：
时间复杂度O(n*m)：每个点都只经过一次。
空间复杂度O(n*m)：只额外申请了一个容器保存每次遍历的点，这个是必须的。但没有申请复杂空间。
具体过程看如下代码: 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mat int整型vector<vector<>> 
     * @return int整型vector
     */
    vector<int> diagonalOrder(vector<vector<int> >& mat) {
        // write code here
        vector<int> res;
        if(mat.size()==0) return res;
        if(mat.size()==1) {//当mat长度为1，说明mat里面只有一个数组
            for(int i=0;i!=mat[0].size();++i) res.push_back(mat[0][i]);
            return res;
        }
        if(mat[0].size()==1) {//当mat[0]长度为1，说明只有1列
            for(int i=0;i!=mat.size();++i) res.push_back(mat[i][0]);
            return res;
        }
        int m=mat.size()-1;
        int n=mat[0].size()-1;
        res.push_back(mat[0][0]);
        int i=0,j=1;
        while(i<=m||j<=n) {//退出循环条件是当i=m&&j=n
            //当i=0或j=n且(i+j)是奇数时，斜向下遍历直到j=0或i=m
            if(((i==0||j==n)&&(i+j)&1)){
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                while(j>0&&i<m) res.push_back(mat[i][j]),++i,--j;
            }
            //当i=0或j=n且(i+j)是偶数时，如果j<n，直接++j;否则++i
            else if((i==0||j==n)&&(i+j)%2==0){
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                if(j<n) res.push_back(mat[i][j]),++j;
                else res.push_back(mat[i][j]),++i;
            }
            //当j=0或i=m且(i+j)是奇数时，如果i<m，++i；否则++j
            if((j==0||i==m)&&(i+j)&1) {
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                if(i<m) res.push_back(mat[i][j]),++i;
                else res.push_back(mat[i][j]),++j;
            } 
            //当j=0或i=m且(i+j)是偶数时，斜向上遍历直到i=0或j=n
            else if((j==0||i==m)&&(i+j)%2==0){
                if(i==m&&j==n) {res.push_back(mat[i][j]);break;}
                while(i>0&&j<n) res.push_back(mat[i][j]),--i,++j;
            }
        }
        return res;
    }
};