「代码随想录算法训练营」第十二天 | 二叉树 part2

226. 翻转二叉树

题目链接:https://leetcode.cn/problems/invert-binary-tree/
题目难度:简单
文章讲解:https://programmercarl.com/0226.翻转二叉树.html
视频讲解:https://www.bilibili.com/video/BV1sP4y1f7q7
题目状态:通过

个人思路:

类似二叉树的层序遍历的变形,创建一个队列,先将根节点压入队列中,当该节点压出队列时,若该节点有左右孩子,将该节点的左右孩子进行翻转(swap),并将其左右孩子节点压入队列中,直到队列中没有节点了,整个循环结束,二叉树翻转完成。

代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        queue<TreeNode *> que;
        que.push(root);
        while(!que.empty()) {
            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;
    }
};

前序遍历实现代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

后序遍历实现代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left, root->right);
        return root;
    }
};

中序遍历实现代码:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        invertTree(root->left);
        swap(root->left, root->right);
        invertTree(root->left);
        return root;
    }
};

101. 对称二叉树

题目链接:https://leetcode.cn/problems/symmetric-tree/
题目难度:简单
文章讲解:https://programmercarl.com/0101.对称二叉树.html
视频讲解:https://www.bilibili.com/video/BV1ue4y1Y7Mf
题目状态:没思路

思路:

使用递归,分别遍历其左孩子是否等于右孩子,若相等,在遍历其左孩子的左孩子是否等于其右孩子的右孩子,以及遍历其左孩子的右孩子是否等于其右孩子的左孩子,若一直进行下去且遍历完成,表示该二叉树是一个对称二叉树。

代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool equal(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;

        bool outside = equal(left->left, right->right);
        bool inside = equal(left->right, right->left);
        bool isSame = outside && inside;
        return isSame;
    }

    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return equal(root->left, root->right);
    }
};

使用迭代方法代码实现(使用两个队列,栈也可以,只需将下面代码中的两个队列改为两个栈即可):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        queue<TreeNode *> que;
        que.push(root->left);
        que.push(root->right);
        while(!que.empty()) {
            TreeNode *leftNode = que.front(); que.pop();
            TreeNode *rightNode = que.front(); que.pop();
            if(!leftNode && !rightNode) continue;
            if(!leftNode || !rightNode || (leftNode->val != rightNode->val)) return false;

            que.push(leftNode->left);
            que.push(rightNode->right);
            que.push(leftNode->right);
            que.push(rightNode->left);
        }
        return true;
    }
};

100. 相同的树

题目链接:https://leetcode.cn/problems/same-tree/
题目难度:简单
题目状态:通过

思路和上一题的思路是一样的,直接看代码:

代码实现:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q != nullptr) return false;
        else if(p != nullptr && q == nullptr) return false;
        else if(p == nullptr && q == nullptr) return true;
        else if(p->val != q->val) return false;
        
        bool leftEqual = isSameTree(p->left, q->left);
        bool rightEqual = isSameTree(p->right, q->right);
        bool isSame = leftEqual && rightEqual;
        return isSame;
    }
};

热门相关:我的女友不可能是怪物   凤惊天之狂妃难求   女配她逆袭了   夫人每天都在线打脸   非人类基因统合体