[LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal

轉自LeetCode

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

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

<Solution>

這題和 Construct Binary Tree from Preorder and Inorder Traversal 類似

只是改成 postorder 和 inorder

思考方式也是一樣，可以用 recursive 來解

• 因為是 postorder (left -> right -> root)，所以由後往前看

• 在 inorder 裡面找到對應的值，左邊的數就在左子樹，右邊的數就在右子樹

舉例

     1
    / \
   2   7
  / \   \
 6   9   8

postorder : [6, 9, 2, 8, 7, 1]

inorder : [6, 2, 9, 1, 7, 8]

詳細說明可以參考 Construct Binary Tree from Preorder and Inorder Traversal

code 如下

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
	return recursive(postorder.size()-1, 0, inorder.size()-1, inorder, postorder);
	}
	TreeNode *recursive(const int &rootPostIdx, const int &inStart, const int &inEnd, vector<int>& inorder, vector<int>& postorder) {
	if(inStart > inEnd || rootPostIdx < 0) {
	return NULL;
	}
	TreeNode *root = new TreeNode(postorder[rootPostIdx]);
	int rootInorderIdx = inStart;
	while(inStart <= inEnd && postorder[rootPostIdx] != inorder[rootInorderIdx]) {
	++rootInorderIdx;
	}
	root->right = recursive(rootPostIdx-1, rootInorderIdx+1, inEnd, inorder, postorder);
	root->left = recursive(rootPostIdx - (inEnd - rootInorderIdx) - 1, inStart, rootInorderIdx-1, inorder, postorder);
	return root;
	}
	};

view raw constructBinaryTreeFromInorderAndPostorderTraversal_1.cpp hosted with ❤ by GitHub

和 Construct Binary Tree from Preorder and Inorder Traversal 一樣，當然也有更快的 iterative 的解法

因為換成 postorder，所以由後往前找，並且先看 right child 再看 left child

其餘的想法都是一樣

code 如下

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
	if(postorder.empty()) {
	return NULL;
	}
	int postIdx = postorder.size()-1, inIdx = inorder.size()-1;
	TreeNode *root = new TreeNode(postorder[postIdx--]);
	stack<TreeNode *> nodeStk;
	nodeStk.push(root);
	while(true) {
	//> all the way down to the deepest right node
	while(nodeStk.top()->val != inorder[inIdx]) {
	TreeNode *rightNode = new TreeNode(postorder[postIdx--]);
	nodeStk.top()->right = rightNode;
	nodeStk.push(rightNode);
	}
	//> backtrace to the node which has left node
	TreeNode *tmpRootNode;
	while(!nodeStk.empty() && nodeStk.top()->val == inorder[inIdx]) {
	tmpRootNode = nodeStk.top();
	nodeStk.pop();
	--inIdx;
	}
	//> terminate
	if(postIdx < 0) {
	break;
	}
	//> connect the left node
	TreeNode *leftNode = new TreeNode(postorder[postIdx--]);
	tmpRootNode->left = leftNode;
	nodeStk.push(leftNode);
	}
	return root;
	}
	};

view raw constructBinaryTreeFromInorderAndPostorderTraversal_2.cpp hosted with ❤ by GitHub