Leetcode.102.Binary Tree Level O

题目

给定一个二叉树, 按层输出节点的值到一个二维数组.

Input: [3,9,20,null,null,15,7]
              3
             / \
            9  20
               / \
              15  7
Output: [[3],[9,20],[15,7]]

思路1

递归, 相当于先序遍历.
效率较低, 空间复杂度较大.

vector<vector<int>> res;
void readTreeNode(TreeNode *root, int level) {
    if (root == nullptr) return;
    cout << root->val << " | level: " << level << endl;
    if (level >= res.size()) {
        res.push_back(vector<int>{});
    }
    res[level].push_back(root->val);
    readTreeNode(root->left, level+1);
    readTreeNode(root->right, level+1);
}

vector<vector<int>> levelOrder(TreeNode* root) {
    readTreeNode(root, 0);
    return res;
}

思路2

使用queue. 每层都将子树加到queue中, 下次输出上次加入的层的值.

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;

    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()) {
        vector<int> vec;
        int size = (int)q.size();
        for (int i = 0; i < size;i++) {
            TreeNode *node = q.front();
            q.pop();
            if (node == nullptr) continue;
            vec.push_back(node->val);
            q.push(node->left);
            q.push(node->right);
        }
        if (!vec.empty()) res.push_back(vec);
    }

    return res;
}

总结

持续优化, 找到更优结果. 循环往往优于递归.
熟练掌握queue.