代码随想录算法训练营day15(day16补) | 二叉树的层序遍历 翻转二叉树 对称二叉树

刷题笔记day15

二叉树的层序遍历

文章讲解：代码随想录
是否自己做出来通过全部用例：是

自己写的代码

迭代法：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if (root) que.push(root);
        while (!que.empty()) {
            vector<int> vec;
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            res.push_back(vec);
        }
        return res;
    }
};

看了题解后写的递归法：

class Solution {
public:
    void traver(vector<vector<int>> &res, int depth, TreeNode* root) {
        if (!root) return;
        if (depth == res.size()) res.push_back(vector<int>());
        res[depth].push_back(root->val) ;
        traver(res, depth+1, root->left);
        traver(res, depth+1, root->right);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        int depth = 0;
        traver(res, depth, root);
        return res;
    }
};

看了题解后的收获

翻转二叉树

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

思路是堆层序遍历的每一层的数据进行翻转，忽略了NULL的情况无法让指针去正确的位置。应该再上一层就进行下一层的翻转。

自己写的代码

看了题解后写的代码：
递归：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return; 
    }
};

层序遍历：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (!root) return root;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* node = que.front();
                que.pop();
                swap(node->left, node->right);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }

        }
        return root;
    }
};

看了题解后的收获

翻转二叉树要在上一层对下一层进行翻转。

对称二叉树

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

自己用了类似于层序遍历，对每层压入vector的元素进行两侧元素是否相等的判断，代码比较复杂，内存占用较多。

自己写的代码

自己写的：

class Solution {
public:
bool isSymmetric(TreeNode* root) {
queue<TreeNode*> que;
if (root == NULL) return true;
que.push(root);
while (!que.empty()) {
int size = que.size();
vector<TreeNode*> vc;
while (size–) {
TreeNode* node = que.front();
que.pop();
vc.push_back(node);
if (node) que.push(node->left);
if (node) que.push(node->right);
}
int left = 0;
int right = vc.size() - 1;
while (left <= right) {
if (vc[left] == NULL && vc[right] == NULL) {
left;
–right;
continue;
}
else if (vc[left] == NULL || vc[right] == NULL) return false;
else {
if (vc[left]->val == vc[right–]->val) continue;
else {
return false;
}
}
}
}
return true;
}
};

迭代法：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> que;
        if (root == NULL) return true;
        que.push(root->left);
        que.push(root->right);
        while (!que.empty()) {
            TreeNode* left = que.front();
            que.pop();
            TreeNode* right = que.front();
            que.pop();
            if (!left && !right) continue;
            if (!left || !right || left->val != right->val) return false;
            que.push(left->left);
            que.push(right->right);
            que.push(left->right);
            que.push(right->left);
        }
        return true;
    }
};

递归法：

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        if (!left && !right) return true;
        if (!left || !right) return false;
        if (left->val != right->val) return false;
        else return compare(left->left, right->right) && compare(left->right, right->left);
    }
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return compare(root->left, root->right);
    }
};

看了题解后的收获

既然是验证对称性，就将元素两两压入queue然后比较。