LeetCode Construct Binary Tree from Inorder and Postorder Traversal

LeetCode Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.


本题要根据树的中序和后序遍历结果,重构出树的结构。

有了之前LeetCode Construct Binary Tree from Preorder and Inorder Traversal根据前序和中序重构树的算法,这一题就是照猫画虎了。因为后序遍历是最后一个数为根节点,和前序遍历其实没本质差别。找准inorder和postorder下标的起止位置就可以开始写代码了:

class Solution {
private:
	TreeNode* dfs(vector<int>& inorder, vector<int>& postorder, int inL, int inR, int postL, int postR, unordered_map<int, int>& hash) {
		if (inL > inR || postL > postR)return NULL;
		TreeNode* root = new TreeNode(postorder[postR]);
		int idx = hash[root->val];
		root->right = dfs(inorder, postorder, inL + 1, inR, postR - (inR - idx), postR - 1, hash);
		root->left = dfs(inorder, postorder, inL, idx - 1, postL, postR - (inR - idx) - 1, hash);
		return root;
	}
public:
	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
		if (inorder.size() == 0)return NULL;
		unordered_map<int, int> hash;
		for (int i = 0; i < inorder.size(); ++i) {
			hash[inorder[i]] = i;
		}
		return dfs(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1, hash);
	}
};

本代码提交AC,用时16MS。

Leave a Reply

Your email address will not be published. Required fields are marked *