3.30华为笔试第三题

寻找完全相同的子树

二叉树中寻找完全相同的子树，返回层数最大的子树
不存在返回-1

样例 输入：

[1,2,3,1,null,2,null,null,null,null,null,1,null,null,null]

输出：

[2,1,null]

#include <iostream>
#include<vector>
#include<queue>
#include<unordered_map>
#include<cmath>
using namespace std;
//生成层序遍历的字符串
string get_ceng(vector<string> vector_tree, int k){
    string res;//返回值
    queue<int> q;
    q.push(k);
    int hangshu = 1;
    while(q.size()){
        string hang_buf="";
        bool flag = false;
        //以行为单位遍历，若该行全为null，舍去
        for(int i=0;i<pow(2,hangshu-1);i++){
            auto t = q.front();
            q.pop();
            if(t>=vector_tree.size()) continue;
            q.push(2*t);q.push(2*t+1);
            if(t!=k) hang_buf+=',';
            hang_buf += vector_tree[t];
            if(vector_tree[t]!="null") flag = true;
        }
        hangshu++;
        if(flag) res += hang_buf;
    }
    return res;
}

int main() {
    //输入字符串
	string s;
	getline(cin,s);
	vector<string> vector_tree;
	vector_tree.push_back("-1");
	//将输入的一行转成vector
	for(int i=0;i<s.size();i++){
	    string buf ="";
	    while(i<s.size() && s[i]!=',')buf+=s[i++];
	    vector_tree.push_back(buf);
	}
	string ans;//声明最后输出的字符串
	unordered_map<string,int>h;//使用哈希表判断是否重复
	queue<int> q;
	q.push(1);
	//遍历所有节点
 	while(q.size()){
	    auto t = q.front();
	    q.pop();
	    string buffer = get_ceng(vector_tree, t);//获取该节点子树的层序遍历
	    //if(buffer != "null")
	    //哈希表存在表明子树重复，记录最大子树
	    if(h[buffer]==1 && buffer.size()>ans.size()) {
	        ans = buffer;
	    }
	    h[buffer]++;
	    if(t*2 < vector_tree.size()) q.push(t*2);
	    if(t*2+1 < vector_tree.size()) q.push(t*2+1);
 	}
	if(ans == "") cout<<"-1";
	else cout<<ans;
	return 0;
}