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

1020 Tree Traversals 更多...

类
struct	TreeNode

函数
int	main (istream &cin, ostream &cout)
TreeNode *	parse (vector< unsigned int > post_order, const vector< unsigned int > &in_order)
	TEST (a1020, case1)

详细描述

1020 Tree Traversals

函数说明

main()

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

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

                                                  {
                unsigned n;
                cin >> n;
                vector<unsigned> post_order(n);
                vector<unsigned> in_order(n);
                for(unsigned i = 0; i < n; i++) {
                    cin >> post_order[i];
                }
                for(unsigned i = 0; i < n; i++) {
                    cin >> in_order[i];
                }
                TreeNode *root = parse(post_order, in_order);
                queue<TreeNode *> q;
                q.push(root);
                bool flag = true;
                while(!q.empty()) {
                    const auto node = q.front();
                    q.pop();
                    if(flag) {
                        flag = false;
                        cout << node->key;
                    } else {
                        cout << ' ' << node->key;
                    }
                    if(node->left != nullptr) {
                        q.push(node->left);
                    }
                    if(node->right != nullptr) {
                        q.push(node->right);
                    }
                }
                return 0;
            }

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

被这些函数引用 TEST().

parse()

TreeNode * pat::a::a1020::parse	(	vector< unsigned int >	post_order,
		const vector< unsigned int > &	in_order
	)

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

                                                                                                   {
                const auto root = new TreeNode(post_order.back());
                bool in_left    = true;
                unordered_set<unsigned> left, right;
                vector<unsigned> left_post, right_post, left_in, right_in;
                for(auto node: in_order) {
                    if(in_left) {
                        if(node == root->key) {
                            in_left = false;
                        } else {
                            left.insert(node);
                            left_in.emplace_back(node);
                        }
                    } else {
                        right.insert(node);
                        right_in.emplace_back(node);
                    }
                }
                for(auto node: post_order) {
                    if(node == root->key) {
                        continue;
                    }
                    if(left.contains(node)) {
                        left_post.emplace_back(node);
                    } else {
                        right_post.emplace_back(node);
                    }
                }
                if(!left.empty()) {
                    root->left = parse(left_post, left_in);
                }
                if(!right.empty()) {
                    root->right = parse(right_post, right_in);
                }
                return root;
            }

引用了 acwing::acwing1929::left, parse(), acwing::acwing1929::right , 以及 acwing::acwing836_408::root.

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

TEST()

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

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

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

引用了 main().