Welcome to BeckoninGshy's Bolg

LeetCode-101. 对称二叉树

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

Solution1（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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) {
        return isMirror(root, root);
    }
    
    bool isMirror(TreeNode* t1, TreeNode* t2){
        //都为NULL
        if(!t1 && !t2) return true;
        //有一个结点为NULL，另一个不为NULL
        if(!t1 || !t2) return false;
        return (t1->val == t2->val) && isMirror(t1->left, t2->right)
            && isMirror(t1->right, t2->left);
    }
};

看的官方题解。

把一棵对称树分成左子树和右子树。

如果左子树和右子树对称，则该数相同。

扩展到一般概念就是：

  • 有两棵树。
  • 两棵树的根节点相同。
  • 每个树的右子树都与另一个树的左子树镜像对称。

翻译为递推公式就是：

1
2
3
4
TreeNode* t1,t2;
t1->val == t2->val;
t1->left == t2->right;
t1->right = t2->left;

结束条件为两棵树为空。

整理可得上述代码。

Solution2（迭代版）：

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
/**
 * 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) {
        queue<TreeNode*> q;
        q.push(root);
        q.push(root);
        while(!q.empty()){
            TreeNode* t1 = q.front(); q.pop();
            TreeNode* t2 = q.front(); q.pop();
            if(!t1 && !t2) continue;
            if(!t1 || !t2) return false;
            if(t1->val != t2->val) return false;
            q.push(t1->left);
            q.push(t2->right);
            q.push(t2->left);
            q.push(t1->right);
            
        }
        return true;
    }
};

翻译为了迭代版，只不过根本的思想是一样的。都是将一棵树化为两棵树来进行判断的。

Solution3（中序迭代版）：

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
/**
 * 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) return true;
        stack<TreeNode*> lefts,rights;
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        while(l || r || lefts.size()){
            while(l && r){
                lefts.push(l),l = l->left;
                rights.push(r), r = r->right;
            }
            if(l || r) return false;
            l = lefts.top();lefts.pop();
            r = rights.top(); rights.pop();
            if(l->val != r->val) return false;
            l = l->right,r = r->left;
        }
        return true;
    }
};
阅读更多
PAT《团体程序设计天梯赛-练习集》-L3-01-二叉搜索树的结-（3-分）

L3-016 二叉搜索树的结构 （30 分）

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）

给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后，得到一棵二叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”（指自顶向下的深度相同）、“2是4的双亲结点”、“3是4的左孩子”都是正确的；而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。

输入格式：

输入在第一行给出一个正整数N（≤100），随后一行给出N个互不相同的整数，数字间以空格分隔，要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M（≤100），随后M行，每行给出一句待判断的陈述句。陈述句有以下6种：

  • A is the root，即”A是树的根”；
  • A and B are siblings，即”A和B是兄弟结点”；
  • A is the parent of B，即”A是B的双亲结点”；
  • A is the left child of B，即”A是B的左孩子”；
  • A is the right child of B，即”A是B的右孩子”；
  • A and B are on the same level，即”A和B在同一层上”。
    题目保证所有给定的整数都在整型范围内。

输出格式：

对每句陈述，如果正确则输出Yes，否则输出No，每句占一行。

Solution：

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;

struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x): val(x), left(NULL), right(NULL){} 
};

int rootval;

void insertNode(TreeNode* root, int val){
	if(!root) return;
	if(root->val > val){
		if(root->left){
			insertNode(root->left,val);
		}else{
			TreeNode* t = new TreeNode(val);
			root->left = t; 
		}
	}else if(root->val < val){
		if(root->right){
			insertNode(root->right,val);
		}else{
			TreeNode* t = new TreeNode(val);
			root->right = t; 
		}
	}
}

bool isContainNode(TreeNode* root, int val){
	if(!root) return false;
	if(root->val == val) return true;
	if(root->val > val) return isContainNode(root->left,val);
	else return isContainNode(root->right,val);
}

void printTree(TreeNode* root){
	if(!root) return;
	cout << root->val <<"";
	printTree(root->left);
	printTree(root->right);
}

bool isRoot(int val){
	return val == rootval;
}

TreeNode* parent(TreeNode *root, int child){
	if(!isContainNode(root,child) || root->val == child) return NULL;
	TreeNode* res = NULL;
	while(1){
		if(!root) return NULL;
		if((root->left && root->left->val == child) || (root->right && root->right->val == child)){
			res = root;
			break;
		}else if(root->val > child){
			root = root->left;
		}else if(root->val < child){
			root = root->right;
		}
	}
	return res;
}

bool isSibling(TreeNode* root, int valA, int valB){
	if(!root) return false;
	if(valA == root->val || valB == root->val) return false;
	//找到A的父亲
	TreeNode* t = parent(root, valA); 
	
	if(t){
		if(t->left && t->left->val == valA ){
			return t->right && t->right->val == valB;
		} 
		else if(t->right && t->right->val == valA ){
			return t->left && t->left->val == valB;
		}else{
			return false;
		}
	}
	return false;
}


int getDepth(TreeNode* root, int val){
	
	if(root->val == val) return 0;
	if(root->val > val) return 1 + getDepth(root->left,val);
	else return 1 + getDepth(root->right,val);
}

bool isSameLevel(TreeNode* root, int A, int B){
//	A != B && 
	return isContainNode(root,A) && isContainNode(root,B) && getDepth(root, A) == getDepth(root, B);
}

void pirntMassage(bool info){
	if(info){
		cout << "Yes" << endl;
	}else{
		cout << "No" <<endl;
	}
}

bool isParent(TreeNode* root, int parentVal, int childVal){
	if(parent(root, childVal) == NULL) return false;
	return parentVal == parent(root, childVal)->val;
}
bool isLeftChild(TreeNode* root, int parentVal, int leftChildVal){
	if(parent(root, leftChildVal) == NULL) return false;
	TreeNode* p = parent(root, leftChildVal);
	return parentVal == p->val && p->left->val == leftChildVal;
}

bool isRightChild(TreeNode* root, int parentVal, int rightChildVal){
	if(parent(root, rightChildVal) == NULL) return false;
	TreeNode* p = parent(root, rightChildVal);
	return parentVal == p->val && p->right->val == rightChildVal;
}

int main(){
	int c;
	cin >> c;
	if(c <= 0) return 0;
	
	cin >> rootval;
	TreeNode* root = new TreeNode(rootval);
	for(int i = 1; i < c; i++){
		int a;
		cin >> a;
		insertNode(root, a);
	}
	
	cin >> c;
	getchar();
	int rootV,siblingA,siblingB, parentv, childv,leftchildv,rightchildv,samelevelA,samelevelB;
 	for(int i = 0 ; i < c; i++){
 		
		char state[100];
		int q = 0;
		char ch;
		while((ch = getchar()) != '\n') state[q++] = ch;
		state[q] = '\0';
		if(strstr(state,"root")){
			sscanf(state,"%d is the root",&rootV);
			pirntMassage(isRoot(rootV));
		}else if(strstr(state,"siblings")){
			sscanf(state,"%d and %d are siblings",&siblingA,&siblingB);
			pirntMassage(isSibling(root,siblingA,siblingB));
		}else if(strstr(state,"same")){
			sscanf(state,"%d and %d are on the same level",&samelevelA,&samelevelB);
			pirntMassage(isSameLevel(root,samelevelA,samelevelB));
		}else if(strstr(state,"parent")){
			sscanf(state,"%d is the parent of %d",&parentv,&childv);
			pirntMassage(isParent(root,parentv,childv));
		}else if(strstr(state,"left")){
			sscanf(state,"%d is the left child of %d",&leftchildv,&parentv);
			pirntMassage(isLeftChild(root,parentv,leftchildv));
		}else if(strstr(state,"right")){
			sscanf(state,"%d is the right child of %d",&rightchildv,&parentv);
			pirntMassage(isRightChild(root,parentv,rightchildv));
		}
	}

//	pirntMassage(isRoot(2));
//	pirntMassage(isSibling(root,1,1));
//	pirntMassage(isSameLevel(root, 0,3));
//	pirntMassage(isParent(root, 3,0));
//	pirntMassage(isLeftChild(root, 2,1));
//	pirntMassage(isRightChild(root, 2,4));
	return 0;
}

第一次写这么多功能的代码，很考验耐力。
没什么大的难点，注意考虑代码的重用性。

第一次用sscanf，还不太熟。

有一坑：它认为 3 and 3 are on the same level。我开始写的时候，直接把这种情况否定掉了。看来盲目做条件判断也不是好事。

阅读更多
PAT《团体程序设计天梯赛-练习集》-L3-01-是否完全二叉搜索-（3-分）

L3-010 是否完全二叉搜索树 （30 分）

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

输入格式：

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

输出格式：

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出YES，如果该树是完全二叉树；否则输出NO。

输入样例1：
1
2
9
38 45 42 24 58 30 67 12 51
输出样例1：
1
2
38 45 24 58 42 30 12 67 51
YES
输入样例2：
1
2
8
38 24 12 45 58 67 42 51
输出样例2：
1
2
38 45 24 58 42 12 67 51
NO

一道考察二叉树插入方法例程，层序遍历，判断是否为一棵完全二叉树的综合题。

Solution：

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
#include<iostream>
#include<vector>
#include<queue>

using namespace std;


struct TreeNode{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; 

void insertNode(TreeNode* root, int val){
	if(root == NULL){
		return;
	}
	if(root->val < val){
		if(root->left == NULL){
			TreeNode* now = new TreeNode(val);
			root->left = now;
		}else{
			insertNode(root->left, val);
		}
	}else if(root->val > val){
		if(root->right == NULL){
			TreeNode* now = new TreeNode(val);
			root->right = now;
		}else{
			insertNode(root->right, val);
		}
	}
}

void levelOrder(TreeNode* root){
	queue<TreeNode*> q;
	q.push(root);
	bool isfirst = true;
	while(!q.empty()){
		TreeNode* node = q.front();
		q.pop();
		if(isfirst){
			cout << node->val;
			isfirst = false;
		}else{
			cout <<  " " << node->val;
		}
		if(node->left) {
			q.push(node->left);
		}
		if(node->right) {
			q.push(node->right);
		}
		
	}
}

bool isCST(TreeNode* root){
	bool leaf = false;
	queue<TreeNode*> q;
	q.push(root);
	while(!q.empty()){
		TreeNode* node = q.front();
		q.pop();
		if(node->right && !node->left) return false;
		if(leaf && (node->left || node->right)) return false;
		if(!node->right && !leaf){
			leaf = true;
		}
		if(node->left) {
			q.push(node->left);
		}
		if(node->right) {
			q.push(node->right);
		}
	}
	return true;
}

void printTree(TreeNode* root){
	if(!root) return;
	printTree(root->left);
	cout << " " << root->val;
	printTree(root->right);
}

int main(){
	int c;
	cin >> c;
	int rootval;
	cin >> rootval;
	TreeNode* root = new TreeNode(rootval);
	for(int i = 1; i < c; i++){
		int nodeval;
		cin >> nodeval;
		insertNode(root, nodeval);
	}
	levelOrder(root);
	cout << endl;
	if(isCST(root)){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
	
	return 0;
}
阅读更多
PAT《团体程序设计天梯赛-练习集》-L3-016 二叉搜索树的结构 （30 分）
algorithm 二叉树 PAT

L3-016 二叉搜索树的结构 （30 分）

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）

阅读更多
PAT《团体程序设计天梯赛-练习集》-L3-010 是否完全二叉搜索树 （30 分）
algorithm 二叉树 PAT

L3-010 是否完全二叉搜索树 （30 分）

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

输入格式：

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

输出格式：

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出YES，如果该树是完全二叉树；否则输出NO。

输入样例1：

1
2
9
38 45 42 24 58 30 67 12 51

输出样例1：

1
2
38 45 24 58 42 30 12 67 51
YES
阅读更多
首页 归档 标签 关于 搜索