106 Construct Binary Tree from Inorder and Postorder Traversal

题目

106 Construct Binary Tree from Inorder and Postorder Traversal

题解

后序遍历的性质：最后一个节点就是树的根节点，左子树的访问先于右子树。中序遍历的性质：根节点左边的节点属于根节点的左子树，根节点右边的节点属于根节点的右子树。对于子树的遍历片段，这两个性质仍然成立。

由于在后序遍历中，左子树的访问先于右子树，所以一旦我们把中序遍历数组的左右子树片段分好，得到右子树片段的长度right length后，就可以直接划分出后序遍历数组的左右子树片段：后序遍历数组里根节点前面right length个节点都是属于右子树的，再往前的全部属于左子树。

有了这些性质，我们可以用下列方法还原出完整的二叉树：

1. 找到二叉树的根节点（没有则为NULL）
2. 把两个遍历数组分成左子树和右子树两部分
3. 对子树进行递归操作
4. 返回找到的根节点

代码

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

private:
	TreeNode* build(vector<int>& inorder, int in_start, int in_end,
		vector<int>& postorder, int post_start, int post_end) {
		if (in_start > in_end) {
			return NULL;
		}

		int root_val = postorder[post_end];
		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 post_divide = in_divide - left_in_start;

		int left_post_start = post_start;
		int left_post_end = left_post_start + post_divide - 1;
		int right_post_start = post_start + post_divide;
		int right_post_end = post_end - 1;

		root->left = build(inorder, left_in_start, left_in_end,
			postorder, left_post_start, left_post_end);
		root->right = build(inorder, right_in_start, right_in_end,
			postorder, right_post_start, right_post_end);
		return root;
	}
};