pat::a::a7_4 命名空间参考

7-4 Pseudo-completeness 更多...

类
struct	Node

函数
Node *	genTree (const vector< int > &preorder, const vector< int > &inorder, int pStart, int pEnd, int iStart, int iEnd)
int	judge (Node *node)
int	main (istream &cin, ostream &cout)
void	postOrder (Node *node, vector< int > &vec)
	TEST (a7_4, case1)
	TEST (a7_4, case2)
	TEST (a7_4, case3)
	TEST (a7_4, case4)

详细描述

7-4 Pseudo-completeness

函数说明

genTree()

Node * pat::a::a7_4::genTree	(	const vector< int > &	preorder,
		const vector< int > &	inorder,
		int	pStart,
		int	pEnd,
		int	iStart,
		int	iEnd
	)

在文件 pat.cpp 第 5213 行定义.

                                    {
                if(pStart > pEnd || iStart > iEnd) {
                    return nullptr;
                }
                const int root = preorder[pStart];
                auto *node     = new Node(root);
                unordered_set<int> lefts;
                int iLeftEnd = iStart;
                while(inorder[iLeftEnd] != root) {
                    lefts.insert(inorder[iLeftEnd++]);
                }
                iLeftEnd--;
                const int iRightStart = iLeftEnd + 2;
                int pLeftEnd          = pStart + 1;
                while(pLeftEnd < preorder.size() && lefts.contains(preorder[pLeftEnd])) {
                    pLeftEnd++;
                }
                node->left  = genTree(preorder, inorder, pStart + 1, pLeftEnd - 1, iStart, iLeftEnd);
                node->right = genTree(preorder, inorder, pLeftEnd, pEnd, iRightStart, iEnd);
                return node;
            }

引用了 genTree() , 以及 acwing::acwing836_408::root.

被这些函数引用 genTree() , 以及 main().

judge()

int pat::a::a7_4::judge

(

Node *

node

)

在文件 pat.cpp 第 5246 行定义.

                                  {
                map<int, int> m;
                vector<vector<Node *>> lvs;
                queue<pair<int, Node *>> q;
                q.push({0, node});
                while(!q.empty()) {
                    const auto p = q.front();
                    q.pop();
                    const int level = p.first;
                    m[level]++;
                    while(lvs.size() < level + 1) {
                        vector<Node *> topush;
                        lvs.push_back(topush);
                    }
                    Node *n = p.second;
                    lvs[level].push_back(n);
                    if(n->left != nullptr) {
                        q.push({level + 1, n->left});
                    }
                    if(n->right != nullptr) {
                        q.push({level + 1, n->right});
                    }
                }
                for(const auto kv: m) {
                    const int k = kv.first;
                    const int v = kv.second;
                    if(k != m.rbegin()->first) {
                        if(v != pow(2, k)) {
                            return 0;
                        }
                    } else {
                        if(v == pow(2, k)) {
                            return 1;
                        }
                        if(lvs.size() >= 2) {
                            bool haveEmpty = false;
                            for(const auto &nd: lvs[lvs.size() - 2]) {
                                if(nd->left == nullptr) {
                                    haveEmpty = true;
                                } else {
                                    if(haveEmpty) {
                                        return 3;
                                    }
                                }
                                if(nd->right == nullptr) {
                                    haveEmpty = true;
                                } else {
                                    if(haveEmpty) {
                                        return 3;
                                    }
                                }
                            }
                        }
                        return 2;
                    }
                }
                return -1;
            }

引用了 pat::a::a7_4::Node::left , 以及 pat::a::a7_4::Node::right.

被这些函数引用 main().

main()

int pat::a::a7_4::main	(	istream &	cin,
		ostream &	cout
	)

在文件 pat.cpp 第 5305 行定义.

                                                  {
                int n;
                cin >> n;
                vector<int> inorder(n);
                vector<int> preorder(n);
                for(int i = 0; i < n; i++) {
                    cin >> inorder[i];
                }
                for(int i = 0; i < n; i++) {
                    cin >> preorder[i];
                }
                Node *root = genTree(preorder, inorder, 0, n - 1, 0, n - 1);
                vector<int> vec;
                cout << judge(root) << endl;
                postOrder(root, vec);
                for(int i = 0; i < vec.size(); i++) {
                    cout << vec[i];
                    if(i != vec.size() - 1) {
                        cout << ' ';
                    }
                }
                return 0;
            }

引用了 genTree(), judge(), postOrder(), acwing::acwing836_408::root , 以及 pat::a::a7_2::vec.

被这些函数引用 TEST().

postOrder()

void pat::a::a7_4::postOrder	(	Node *	node,
		vector< int > &	vec
	)

在文件 pat.cpp 第 5236 行定义.

                                                         {
                if(node->left != nullptr) {
                    postOrder(node->left, vec);
                }
                if(node->right != nullptr) {
                    postOrder(node->right, vec);
                }
                vec.emplace_back(node->val);
            }

引用了 pat::a::a7_4::Node::left, postOrder(), pat::a::a7_4::Node::right, pat::a::a7_4::Node::val , 以及 pat::a::a7_2::vec.

被这些函数引用 main() , 以及 postOrder().

TEST() [1/4]

pat::a::a7_4::TEST	(	a7_4	,
		case1
	)

在文件 pat_test.cpp 第 2356 行定义.

                              {
                istringstream in("7\n"
                                 "4 2 5 1 6 3 7\n"
                                 "1 2 4 5 3 6 7");
                auto out = ostringstream();
                main(in, out);
                ASSERT_EQ("1\n"
                          "4 5 2 6 7 3 1",
                          out.str());
            }

引用了 main().

TEST() [2/4]

pat::a::a7_4::TEST	(	a7_4	,
		case2
	)

在文件 pat_test.cpp 第 2367 行定义.

                              {
                istringstream in("10\n"
                                 "8 4 9 2 10 5 1 6 3 7\n"
                                 "1 2 4 8 9 5 10 3 6 7");
                auto out = ostringstream();
                main(in, out);
                ASSERT_EQ("2\n"
                          "8 9 4 10 5 2 6 7 3 1",
                          out.str());
            }

引用了 main().

TEST() [3/4]

pat::a::a7_4::TEST	(	a7_4	,
		case3
	)

在文件 pat_test.cpp 第 2378 行定义.

                              {
                istringstream in("10\n"
                                 "8 4 2 5 11 1 6 3 14 7\n"
                                 "1 2 4 8 5 11 3 6 7 14");
                auto out = ostringstream();
                main(in, out);
                ASSERT_EQ("3\n"
                          "8 4 11 5 2 6 14 7 3 1",
                          out.str());
            }

引用了 main().

TEST() [4/4]

pat::a::a7_4::TEST	(	a7_4	,
		case4
	)

在文件 pat_test.cpp 第 2389 行定义.

                              {
                istringstream in("7\n"
                                 "4 2 10 5 1 3 7\n"
                                 "1 2 4 5 10 3 7");
                auto out = ostringstream();
                main(in, out);
                ASSERT_EQ("0\n"
                          "4 10 5 2 7 3 1",
                          out.str());
            }

引用了 main().