LeetCode 101. Symmetric Tree

发表于 | 分类于 ，
字数统计： 6.6k | 阅读时长≈ 0:07

LeetCode 101. Symmetric Tree

Description:

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Example 1:

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
/ \
2 2
/ \ / \
3 4 4 3

Example 2:

But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3

分析：

其实这道题可以参考LeetCode 100. Same Tree类似的解法，首先我们判断树的根节点，然后把左右子树看成和Same Tree一样求两棵树是否一样，只不过此时p->left==r->left换成p->left==r->right，p->right==r->right换成p->right==r->left。

这道题最麻烦的还是写main函数测试样例时构造二叉树的问题，又提醒我要复习一下数据结构的知识，最终我找了两个构造二叉树的方法，两个版本的代码在底下都可以看到；
另外我还把LeetCode.com上面自带的测试main函数放在这个博客里，人家的代码写得就是吊，用到了很多标准库函数，把样例作为字符串输入，然后处理字符串构造二叉树。666

代码如下：

one version：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <malloc.h>
using namespace std;
/**
 * 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:
	bool isSymmetric(TreeNode* root) {
		if (root == NULL) return true;
		return isMirror(root->left, root->right);
	}
	bool isMirror(TreeNode* p, TreeNode* q) {
		if (p == NULL && q == NULL) return true;
		else if (p != NULL && q != NULL && p->val == q->val && isMirror(p->left, q->right) && isMirror(p->right, q->left))
			return true;
		else return false;
	}
};
// 构造二叉树
void TreeNodeCreate(TreeNode **tp) {
	// 构造方法，或者说构造顺序：从左子树开始构造
	int x;
	cin >> x;
	if(x < 0) {
		*tp = NULL;// 指针为空，树节点中的某个指针为空
		return;
	}
	*tp = (TreeNode*)malloc(sizeof(TreeNode));// 将树节点中指针指向该地址空间
	if(tp == NULL) return;
	(*tp)->val =x;
	TreeNodeCreate(&((*tp)->left));
	TreeNodeCreate(&((*tp)->right));
}

int main() {
	Solution s;
	TreeNode* tree;
	TreeNodeCreate(&tree);
	cout << s.isSymmetric(tree) << endl;
	return 0;
}
/*
input:
1
2
3
-1 -1
4
-1 -1
2
4
-1 -1
3
-1 -1

output:
1
 */

/*
input:
1
2
-1
3
-1 -1
2
-1 3
-1 -1

output:
0
 */

another version:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <malloc.h>
using namespace std;
/**
 * 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:
	bool isSymmetric(TreeNode* root) {
		if (root == NULL) return true;
		return isMirror(root->left, root->right);
	}
	bool isMirror(TreeNode* p, TreeNode* q) {
		if (p == NULL && q == NULL) return true;
		else if (p != NULL && q != NULL && p->val == q->val && isMirror(p->left, q->right) && isMirror(p->right, q->left))
			return true;
		else return false;
	}
};
// 构造二叉树
int TreeNodeCreate(TreeNode* &tree) {
	int val;
	cin >> val;
	if (val < 0) // 小于0表示空节点
		tree = NULL;
	else {
		tree = new TreeNode(val); // 创建根节点
		tree->val = val;
		TreeNodeCreate(tree->left); // 创建左子树
		TreeNodeCreate(tree->right);// 创建右子树
	}
	return 0;
}
int main() {
	Solution s;
	TreeNode* tree;
	TreeNodeCreate(tree);
	cout << s.isSymmetric(tree) << endl;
	return 0;
}
/*
input:
1
2
3
-1 -1
4
-1 -1
2
4
-1 -1
3
-1 -1

output:
1
 */

/*
input:
1
2
-1
3
-1 -1
2
-1 3
-1 -1

output:
0
 */

one more version from LeetCode.com:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
/**
 * 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:
	bool isSymmetric(TreeNode* root) {
		if (root == NULL) return true;
		return isMirror(root->left, root->right);
	}
	bool isMirror(TreeNode* p, TreeNode* q) {
		if (p == NULL && q == NULL) return true;
		else if (p != NULL && q != NULL && p->val == q->val && isMirror(p->left, q->right) && isMirror(p->right, q->left))
			return true;
		else return false;
	}
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

TreeNode* stringToTreeNode(string input) {
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    if (!input.size()) {
        return nullptr;
    }

    string item;
    stringstream ss;
    ss.str(input);

    getline(ss, item, ',');
    TreeNode* root = new TreeNode(stoi(item));
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);

    while (true) {
        TreeNode* node = nodeQueue.front();
        nodeQueue.pop();

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int leftNumber = stoi(item);
            node->left = new TreeNode(leftNumber);
            nodeQueue.push(node->left);
        }

        if (!getline(ss, item, ',')) {
            break;
        }

        trimLeftTrailingSpaces(item);
        if (item != "null") {
            int rightNumber = stoi(item);
            node->right = new TreeNode(rightNumber);
            nodeQueue.push(node->right);
        }
    }
    return root;
}

string boolToString(bool input) {
    return input ? "True" : "False";
}

int main() {
    string line;
    while (getline(cin, line)) {
        TreeNode* root = stringToTreeNode(line);
        
        bool ret = Solution().isSymmetric(root);

        string out = boolToString(ret);
        cout << out << endl;
    }
    return 0;
}
// this one is from LeetCode.com
/*
input:
[1,2,2,3,4,4,3]

output:
True
 */

/*
input:
[1,2,2,null,3,null,3]

output:
False
 */
------本文结束感谢阅读------