文章

8

粉丝

14

获赞

1

访问

7.6k

头像
判断二叉树是否对称 题解:
P1551 东北大学机试题
发布于2024年8月31日 17:21
阅读数 917

将层序遍历的字符串反序列化,构造成二叉链表形式的二叉树

再通过isSymmetric和isMirror两个函数判断是否对称

(我的这两个函数感觉相对来说要更容易理解一下) 

P.S 代码中的l是list<int>链表,用来存储层序遍历的字符串输入,方便获取和删除头部元素(l.front()和l.pop_front())

#include<bits/stdc++.h>
using namespace std;

struct node {
	char val;
	node* left;
	node* right;
	node() {}
	node(char x) : val(x), left(nullptr), right(nullptr) {}
};

node* deserialize(list<char>& l) {
	queue<node*> q;
	if(l.front() == '#')
		return nullptr;
		
	auto root = new node(l.front());
	l.pop_front();
	q.push(root);
	
	while(!l.empty() && !q.empty()) {
		auto n = q.front();
		q.pop();
		
		char cl = l.front();
		l.pop_front();
		if(cl != '#') {
			n->left = new node(cl);
			q.push(n->left);
		}
		
		//这里最好再次检查 !l.empty() 
		char cr = l.front();
		l.pop_front();
		if(cr != '#') {
			n->right = new node(cr);
			q.push(n->right);
		}
		
	}
	return root;
}
bool isMirror(node* t1, node* t2) {
	if(t1 == nullptr...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发