讨论/《初级算法》 - 二叉树的层序遍历/
《初级算法》 - 二叉树的层序遍历

C++ 递归做法

class Solution {
public:
    void Push(vector<vector<int>> &ret, TreeNode* p, TreeNode* q, int count) {
        count++; //指示应该push_back到哪一行
        /* if判断条件 
            1.ret的行数和遍历到的节点在树中的行数不等
            2.ret的行数不大于遍历到的节点在树中的行数
            3.遍历的节点不是最后的空节点
            满足以上条件则创建新的ret行
        */
        if((ret.size()-1 != count) && ret.size()-1 < count && (p || q)) {
            vector<int> asd;
            ret.push_back(asd);
        }
        if(p) {
            ret[count].push_back(p->val);
            Push(ret, p->left, p->right, count);
        }
        if(q) {
            ret[count].push_back(q->val);
            Push(ret, q->left, q->right, count);
        }
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > ret;
        if(root) {
            //root不为空,插入第一行
            vector<int> asd;
            ret.push_back(asd);
            int count = 0;
            ret[0].push_back(root->val);
            //调用递归函数
            Push(ret, root->left, root->right, count);
        }
        return ret;
    }
};

image.png

展开全部 19 讨论