102-二叉树的层序遍历

LeetCode 102. Binary Tree Level Order Traversal

LeetCode-102

Given the root of a binary tree, return the level order traversal of its nodes’ values.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

method 1: 队列

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    if (root == nullptr) return ret;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();    // 先记录size，后面会变
        vector<int> path;
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = q.front();
            q.pop();
            path.push_back(cur->val);
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        ret.push_back(vec);
    }
    return ret;
}

method 2: 递归

先序遍历，把节点插入到相同深度的vector中

后面要索引，所以先插入一个空的vector

vector<vector<int>> res;
void traversal(TreeNode* cur, int depth) {
    if (!cur) return;
    if (res.size() == depth) {
        res.push_back(vector<int>());   // 先插入一个空的vector
    }
    res[depth].push_back(cur->val);
    if (cur->left) traversal(cur->left, depth + 1);
    if (cur->right) traversal(cur->right, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
    traversal(root, 0);
    return res;
}

---

LeetCode 103. Binary Tree Zigzag Level Order Traversal

LeetCode-103

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

method

奇数层的vector要反转

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;  // 记录深度
    while (!q.empty()) {
        int size = q.size();
        vector<int> path;
        for (int i = 0; i < size; i++) {
            TreeNode *cur = q.front();
            q.pop();
            path.push_back(cur->val);
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        if (depth % 2) reverse(path.begin(), path.end());   // 反转
        res.push_back(path);
        depth++;    // 深度增加
    }
    return res;
}

---

LeetCode 107. Binary Tree Level Order Traversal II

LeetCode-107

Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values. (i.e., from left to right, level by level from leaf to root).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

method

层序遍历最后反转即可

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ret;
    if (root == nullptr) return ret;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        vector<int> path;
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = q.front();
            q.pop();
            path.push_back(cur->val);
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        ret.push_back(vec);
    }
    reverse(ret.begin(), ret.end());    // 最后反转即可
    return ret;
}

LeetCode 199. Binary Tree Right Side View

LeetCode-199

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1:

Input: 
   1        <---
 /   \
2     3     <---
 \     \
  5     4   <---
Output: [1, 3, 4]

method

每层遍历到最右边的时候记录节点

vector<int> rightSideView(TreeNode* root) {
    vector<int> ret;
    if (root == nullptr) return ret;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = q.front();
            q.pop();
            if (i == size - 1) ret.push_back(cur->val); // 最右边的位置
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return ret;
}

---

LeetCode 429. N-ary Tree Level Order Traversal

LeetCode-429

Given an n-ary tree, return the level order traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [[1],[3,2,4],[5,6]]

method

遍历每个节点的子节点

vector<vector<int>> levelOrder(Node* root) {
    queue<Node*> q;
    vector<vector<int>> ret;
    if (root == nullptr) return ret;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        vector<int> vec;
        for (int i = 0; i < size; ++i) {
            Node* cur = q.front();
            q.pop();
            vec.push_back(cur->val);
            for (int j = 0; j < cur->children.size(); ++j) {
                q.push(cur->children[j]);
            }
        }
        ret.push_back(vec);
    }
    return ret;
}

---

LeetCode 637. Average of Levels in Binary Tree

LeetCode-637

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within $10^{-5}$ of the actual answer will be accepted.

Example 1:

Input: 
    3
   / \
  9  20
    /  \
   15   7
Output: [3.00000,14.50000,11.00000]

method

记录每层的节点总和，遍历完一层后记录平均值

vector<double> averageOfLevels(TreeNode* root) {
    vector<double> ret;
    if (root == nullptr) return ret;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        double sum = 0;
        for (int i = 0; i < size; ++i) {
            TreeNode* cur = q.front();
            q.pop();
            sum += cur->val;
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        ret.push_back(sum / size);
    }
    return ret;