【算法刷题day14】层次遍历、226.翻转二叉树、101.对称二叉树

102.二叉树的层序遍历(opens new window)
107.二叉树的层次遍历II(opens new window)
199.二叉树的右视图(opens new window)
637.二叉树的层平均值(opens new window)
429.N叉树的层序遍历(opens new window)
515.在每个树行中找最大值(opens new window)
116.填充每个节点的下一个右侧节点指针(opens new window)
117.填充每个节点的下一个右侧节点指针II(opens new window)
104.二叉树的最大深度(opens new window)
111.二叉树的最小深度

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> qu;
        vector<vector<int>> res;
        if(root != nullptr)qu.push(root);
        while(!qu.empty()){
            int size = qu.size();
            vector<int> vec;
            for(int i = 0; i < size; i++){
                TreeNode* node = qu.front();
                qu.pop();
                if(node -> left)qu.push(node -> left);
                if(node -> right)qu.push(node -> right);
                vec.push_back(node -> val);
            }
            res.push_back(vec);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

226.翻转二叉树

文档链接：[代码随想录]
题目链接：226.翻转二叉树
状态：ok

题目：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr)return root;
        swap(root -> left, root -> right);
        invertTree(root -> left);
        invertTree(root -> right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10

101.对称二叉树

文档链接：[代码随想录]
题目链接：101.对称二叉树
状态：递归还是不太会

题目：
给定一个二叉树，检查它是否是镜像对称的。

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23