acwing::acwing18 命名空间参考

函数
TreeNode *	buildTree (vector< int > &preorder, vector< int > &inorder)
TreeNode *	rebuild (vector< int > &inorder, int in_begin, int in_end, vector< int > &preorder, int pre_begin, int pre_end)

函数说明

buildTree()

TreeNode * acwing::acwing18::buildTree	(	vector< int > &	preorder,
		vector< int > &	inorder
	)

在文件 acwing408.cpp 第 426 行定义.

                                                                         {
            if(preorder.empty() || inorder.empty()) {
                return nullptr;
            }
            return rebuild(inorder, 0, inorder.size() - 1, preorder, 0, preorder.size() - 1);
        }

引用了 rebuild().

rebuild()

TreeNode * acwing::acwing18::rebuild	(	vector< int > &	inorder,
		int	in_begin,
		int	in_end,
		vector< int > &	preorder,
		int	pre_begin,
		int	pre_end
	)

在文件 acwing408.cpp 第 394 行定义.

                                                                                                                             {
            if(in_begin == in_end) {
                return new TreeNode(inorder[in_begin]);
            }
            TreeNode *root = new TreeNode(preorder[pre_begin]);
 
            int left_in_cursor  = in_begin;
            int left_pre_cursor = pre_begin + 1;
 
            if(inorder[in_begin] == preorder[pre_begin]) {
                root->left = nullptr;
            } else {
                unordered_set<int> left = unordered_set<int>();
                while(inorder[left_in_cursor] != preorder[pre_begin]) {
                    left.insert(inorder[left_in_cursor]);
                    left_in_cursor++;
                }
                while(left.find(preorder[left_pre_cursor]) != left.end()) {
                    left_pre_cursor++;
                }
                root->left = rebuild(inorder, in_begin, left_in_cursor - 1, preorder, pre_begin + 1, left_pre_cursor - 1);
            }
 
            if(inorder[in_end] == preorder[pre_begin]) {
                root->right = nullptr;
            } else {
                root->right = rebuild(inorder, left_in_cursor + 1, in_end, preorder, left_pre_cursor, pre_end);
            }
 
            return root;
        }

引用了 acwing::acwing1929::left, acwing::TreeNode::left, rebuild(), acwing::TreeNode::right , 以及 acwing::acwing3786::root.

被这些函数引用 buildTree() , 以及 rebuild().