LeetCode Hot100 | Day3 | 二叉树：翻转二叉树&&对称二叉树

226.翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

后序遍历交换两个结点就行

完整代码：

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

101.对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

层序遍历来做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode *> q;
        if(root==nullptr)
            return true;
        q.push(root->left);
        q.push(root->right);
        while(!q.empty())
        {
            TreeNode *t1=q.front();
            q.pop();
            TreeNode *t2=q.front();
            q.pop();
            if(t1==nullptr&&t2==nullptr)
                continue;
            else if(t1==nullptr&&t2!=nullptr)
                return false;
            else if(t1!=nullptr&&t2==nullptr)
                return false;
            else if(t1!=nullptr&&t2!=nullptr)
                if(t1->val!=t2->val)
                    return false;
            else 
                q.push(t1->left);
                q.push(t2->right);
                q.push(t1->right);
                q.push(t2->left);
        }
        return true;
    }
};

递归法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool is(TreeNode *l,TreeNode *r)
    {
        if(l==nullptr&&r==nullptr)
            return true;
        else if(l!=nullptr&&r==nullptr)
            return false;
        else if(l==nullptr&&r!=nullptr)
            return false;
        else if(l->val!=r->val)
            return false;
        bool left=is(l->left,r->right);
        bool right=is(l->right,r->left);
        return left&&right;
    }
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr)
            return true;
        return is(root->left,root->right);
    }
};

（代码随想录DAY16）