102.Binary Tree Level Order Traversal¶

102.Binary Tree Level Order Traversal¶

Tags: Tree Medium

Link: https://leetcode.com/problems/binary-tree-level-order-traversal/

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree [3,9,20,null,null,15,7],

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Answer:

使用一个辅助队列来存储下一层：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;

        stack<TreeNode *> cur, next;
        cur.push(root);
        vector<int> level;

        while (!cur.empty()) {
            while (!cur.empty()) {
                TreeNode * p = cur.top();
                cur.pop();
                level.push_back(p -> val);
                if (p -> right) next.push(p -> right);
                if (p -> left) next.push(p -> left);
            }
            reverse(level.begin(), level.end());
            res.push_back(level);
            level.clear();
            std::swap(cur, next);
        }

        return res;
    }
};

时间复杂度：O(n), 空间复杂度O(1)。

因为需要清空vector的操作和交换两个队列元素的操作，比较耗时间。所以可以考虑把两个队列合并成一个，增加一个计数器来记录每一层元素的数量，余下的就是下一层的元素。时间复杂度O(n)，空间复杂度O(1);

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //迭代法，时间复杂度O(n)，空间复杂度O(1)
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root == nullptr) return result;

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

        while(!cur.empty()){
            vector<int> tmp; //构建一个一维vector来存储每一层

            for(int i = cur.size(); i > 0; --i){
                TreeNode *p = cur.front();
                cur.pop();
                tmp.push_back(p -> val);

                if(p -> left != nullptr) cur.push(p -> left);
                if(p -> right != nullptr) cur.push(p -> right);
            }
            result.push_back(tmp);
        }

        return result;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Binary Tree Level Order Traversal.
Memory Usage: 13.9 MB, less than 83.10% of C++ online submissions for Binary Tree Level Order Traversal.

递归解法：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;

        levelOrder(root, 0, res);

        return res;
    }

    void levelOrder(TreeNode *root, size_t level, vector<vector<int>> & res) {
        if (res.size() == level) res.push_back(vector<int>());
        res[level].push_back(root -> val);
        if (root -> left) levelOrder(root -> left, level + 1, res);
        if (root -> right) levelOrder(root -> right, level + 1, res);
    }
};

由于递归的特性，会一直深度优先去处理左子结点，那么势必会穿越不同的层，所以当要加入某个结点的时候，必须要知道当前的深度，所以使用一个变量level来标记当前的深度，初始化代入0，表示根结点所在的深度。由于需要返回的是一个二维数组res，开始时又不知道二叉树的深度，不知道有多少层，所以无法实现申请好二维数组的大小，只有在遍历的过程中不断的增加。那么我们什么时候该申请新的一层了呢，当level等于二维数组的大小的时候，为啥是等于呢，不是说要超过当前的深度么，这是因为level是从0开始的，就好比一个长度为n的数组A，你访问A[n]是会出错的，当level等于数组的长度时，就已经需要新申请一层了，我们新建一个空层，继续往里面加数字，