Cinte's Leetcode Record
0%

剑指 Offer 27. 二叉树的镜像

Posted on Edited on In Disqus:
Symbols count in article: 934 Reading time ≈ 1 mins.

剑指 Offer 27. 二叉树的镜像

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)
            return nullptr;
        swap(root->left, root->right);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};
迭代
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)
            return nullptr;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty())
        {
            auto p = s.top();
            s.pop();
            if(p->left)
                s.push(p->left);
            if(p->right)
                s.push(p->right);
            swap(p->right, p->left);
        }        
        return root;
    }
};