102BinaryTreeLevelOrderTraversal.org

[#B] 102 Binary Tree Level Order Traversal - LeetCode

Java

解法一

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levelOrder = new ArrayList();
        if (root == null) return levelOrder;
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int level = queue.size();
            List<Integer> levelList = new ArrayList();
            // level 就是每一层的数量
            for (int i = 0; i < level; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                levelList.add(node.val);
            }

            levelOrder.add(levelList);

        }

        return levelOrder;
    }
}

解法二

记录每个节点的层级，添加到对应的列表中

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class LevelTreeNode {
    int level;
    TreeNode node;

    LevelTreeNode(TreeNode node, int level) {
        this.node = node;
        this.level = level;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levelOrder = new ArrayList();
        if (root == null) return levelOrder;
        Queue<LevelTreeNode> queue = new LinkedList();
        queue.offer(new LevelTreeNode(root, 0));
        while (!queue.isEmpty()) {
            LevelTreeNode levelNode = queue.poll();
            int level = levelNode.level;
            TreeNode node = levelNode.node;

            if (level == levelOrder.size()) {
                levelOrder.add(new ArrayList());
            }

            List<Integer> levelList = levelOrder.get(level);
            levelList.add(node.val);

            if (node.left != null) {
                queue.offer(new LevelTreeNode(node.left, level + 1));
            }

            if (node.right != null) {
                queue.offer(new LevelTreeNode(node.right, level + 1));
            }
        }

        return levelOrder;
    }

}

CPP

解法一

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == NULL) return res;
        queue<pair<TreeNode*, int>> q;
        q.push(make_pair(root, 0));
        while (!q.empty()) {
            TreeNode* node = q.front().first;
            int level = q.front().second;
            q.pop();
        
            if (level == res.size()) {
                res.push_back(vector<int>());
            }
        
            if (node->left != NULL) q.push(make_pair(node->left, level + 1));
            if (node->right != NULL) q.push(make_pair(node->right, level + 1));
        
            res[level].push_back(node->val);
        }
        return res;
    }
};

解法二

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) return res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            vector<int> level;
            for (int i = 0; i < size; ++i) {
                auto node = q.front();
                q.pop();
                if (node->left != nullptr) q.push(node->left);
                if (node->right != nullptr) q.push(node->right);
                level.push_back(node->val);
            }
            res.push_back(level);
        }
        return res;
    }
};