政子的博客

技术|学习|随笔

CodingInterview-二叉树镜像

最容易想到的就是递归的思路了，对树进行递归，同时调整左右子树的顺序。

既然剑指上面的题目基本都是使用 C++ 的，那我也稍微捡起来很多年没用的 C++ 试试好了。

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
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot==nullptr){
            return;
        }
        if(pRoot->left!=nullptr){
            Mirror(pRoot->left);
        }
        if(pRoot->right!=nullptr){
            Mirror(pRoot->right);
        }
        auto temp=pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=temp;
    }
};

而理论上只要把树上的节点都遍历到了，都是可以的。所以也可以很方便地用循环来完成题目，用栈或者队列都行。

PS:一定要注意最开始 pRoot 是否为 NULL 的判断

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
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if(pRoot==nullptr){
            return;
        }
        queue<TreeNode*> q;
        q.push(pRoot);
        while(!q.empty()){
            TreeNode* f=q.front();
            q.pop();
            TreeNode* t=f->left;
            f->left=f->right;
            f->right=t;
            if(f->left!=nullptr){
                q.push(f->left);
            }
            if(f->right!=nullptr){
                q.push(f->right);
            }
        }
    }
};