二叉树|102.二叉树层序遍历、226.翻转二叉树、101.对称二叉树

102.二叉树层序遍历

自己审题思路

使用队列来维护每一层的节点

看完代码随想录题解后的收获

层序遍历的递归法和延伸题目

代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.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);
            }
            result.push_back(vec);
        }
        return result;
    }
};

代码（递归）

class Solution {
public:
    void dfs(TreeNode* cur, vector<vector<int>>& vec, int depth) {
        if (cur == nullptr) return;
        if (vec.size() < depth) vec.push_back(vector<int>());
        vec[depth - 1].push_back(cur->val);
        dfs(cur->left, vec, depth + 1);
        dfs(cur->right, vec, depth + 1);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(root, ans, 1);
        return ans;
    }
};

递归法还是使用的dfs，但是给每层加了一个depth标志（从1开始），每次遍历到depth层时，向二维数组的depth-1行（因为数组下标从0开始）加入元素。每当二维数组的大小（行数）小于depth时，表明遍历到了新的一行，添加一行（添加一个空数组进去）。

参考详解

226.翻转二叉树

自己审题思路

遍历过程中swap左右孩子

看完代码随想录题解后的收获

不能使用中序遍历实现翻转

代码：

class Solution {
public:
    void dfs(TreeNode* cur) {
        if (cur == nullptr) return;
        swap(cur->left, cur->right);
        dfs(cur->left);
        dfs(cur->right);
    }
    TreeNode* invertTree(TreeNode* root) {
        dfs(root);
        return root;
    }
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            int size = que.size();

            for (int i = 0; i < size; i++) {
                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;
    }
};

参考详解

101.对称二叉树

自己审题思路

判断左右子树是否对称可以使用递归思想

看完代码随想录题解后的收获

具体的实现思路（各种方案的实现思路-----dfs，bfs，递归）

代码：

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

        return compare(left->left, right->right) && compare(left->right, right->left);
    }
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) return true;
        return compare(root->left, root->right);
    }
};

参考详解

今日感悟

树结构的操作常用到递归思想