105 Construct Binary Tree from Preorder and Inorder Traversal

题目

105 Construct Binary Tree from Preorder and Inorder Traversal

题解

先序遍历的性质：第一个节点就是树的根节点，左子树的访问先于右子树。中序遍历的性质：根节点左边的节点属于根节点的左子树，根节点右边的节点属于根节点的右子树。

利用这两种遍历的性质，我们可以找到二叉树的根节点，并把中序遍历数组分成左子树和右子树两部分。由于在先序遍历中，左子树的访问先于右子树，所以在通过中序遍历数组确定了左子树的长度left length后，先序遍历数组中根节点的后left length个节点都是属于左子树的，再往后的全部节点属于右子树。

对于子树，我们同样能根据先序遍历数组和中序遍历数组中对应的片段确定子树的根节点并将子树进一步划分成左子树和右子树。因此，我们只要递归地进行寻找根节点并划分左右子树的操作，就能还原出整颗二叉树。

代码

class Solution {
public:
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		return build(preorder, 0, preorder.size() - 1,
			inorder, 0, inorder.size() - 1);
	}

private:
	TreeNode* build(vector<int>& preorder, int pre_start, int pre_end,
		vector<int>& inorder, int in_start, int in_end) {
		if (in_start > in_end) {
			return NULL;
		}

		int root_val = preorder[pre_start];
		TreeNode* root = new TreeNode(root_val);

		int in_divide;
		for (in_divide = in_start; in_divide <= in_end; in_divide++) {
			if (inorder[in_divide] == root_val) {
				break;
			}
		}

		int left_in_start = in_start;
		int left_in_end = in_divide - 1;
		int right_in_start = in_divide + 1;
		int right_in_end = in_end;

		int left_pre_length = in_divide - left_in_start - 1;

		int left_pre_start = pre_start + 1;
		int left_pre_end = left_pre_start + left_pre_length;
		int right_pre_start = left_pre_end + 1;
		int right_pre_end = pre_end;

		root->left = build(preorder, left_pre_start, left_pre_end,
			inorder, left_in_start, left_in_end);
		root->right = build(preorder, right_pre_start, right_pre_end,
			inorder, right_in_start, right_in_end);
		return root;
	}
};