day14 二叉树2

226.翻转二叉树

递归法：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return root;
        }
        TreeNode *temp = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(temp);
        return root;
    }
};

迭代法：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return root;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            TreeNode *node = q.front();
            q.pop_front();
            swap(node->left, node->right);
            if (node->left) {
                q.push_back(node->left);
            }
            if (node->right) {
                q.push_back(node->right);
            }
        }
        return root;
    }
};

101. 对称二叉树

递归法：

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

    bool isSymmetric(TreeNode* root) {
        return recur(root->left, root->right);
    }
};

迭代法（写得好麻烦。。。。。还用了个vector）：

class Solution {
public:
    bool vecSymmetric(vector<int> &vec) {
        for (int i = 0, j = vec.size() - 1; i < j; i ++, j --) {
            if (vec[i] != vec[j]) {
                return false;
            }
        }
        return true;
    }

    bool isSymmetric(TreeNode* root) {
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            int n = q.size();
            vector<int> vec;
            bool flag = false;
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                if (node != nullptr) {
                    vec.push_back(node->val);
                    q.push_back(node->left);
                    q.push_back(node->right);
                    flag = true;
                }
                else {
                    vec.push_back(-101);
                    q.push_back(nullptr);
                    q.push_back(nullptr);
                }
            }
            if (flag == false) {
                return true;
            }
            if (vecSymmetric(vec) == false) {
                return false;
            }
        }
        return true;
    }
};

优化版：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        deque<TreeNode*> q;
        q.push_back(root->left);
        q.push_back(root->right);
        while (!q.empty()) {
            TreeNode *leftNode = q.front();
            q.pop_front();
            TreeNode *rightNode = q.front();
            q.pop_front();
            if (leftNode == nullptr && rightNode == nullptr) {
                continue;
            }
            if (leftNode == nullptr || rightNode == nullptr || leftNode->val != rightNode->val) {
                return false;
            }
            q.push_back(leftNode->left);
            q.push_back(rightNode->right);
            q.push_back(leftNode->right);
            q.push_back(rightNode->left);
        }
        return true;
    }
};

104.二叉树的最大深度

递归法day13写了
迭代法：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int res = 0;
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            res ++;
            int n = q.size();
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
        }
        return res;
    }
};

111.二叉树的最小深度

递归法（day13没写明白，今天再试试！）：

class Solution {
public:
    int recur(TreeNode *node) {
        if (node == nullptr) {
            return 0;
        }
        if (node->left != nullptr && node->right != nullptr) {
            return 1 + min(recur(node->left), recur(node->right));
        }
        if (node->left) {
            return 1 + recur(node->left);
        }
        return 1 + recur(node->right);
    }
    
    int minDepth(TreeNode* root) {
        return recur(root);
    }
};

迭代法：

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        int res = 0;
        while (!q.empty()) {
            int n = q.size();
            res ++;
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                if (node->left == nullptr && node->right == nullptr) {
                    return res;
                }
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
        }
        return res;
    }
};