[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal

轉自 LeetCode

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

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

<Solution>

這題要我們從 preorder 和 inorder traversal 兩個資訊中，把 binary tree 給重建出來

這邊先注意到題目有說，不會有重複的元素

因為有這個前題條件，我們可以找出 preorder traversal 中的某個值，在 inorder traversal 中的位置

舉例

     1
    / \
   2   7
  / \   \
 6   9   8

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

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

因為 preorder 的特性，preorder[0] = 1 一定是 root

找出 1 在 inorder 的位置，index = 4，inorder[4] = 1

那麼，inorder[0] 到 inorder[3] 一定是在 inorder[4] 的左子樹

inorder[5] 到 inorder[6] 一定是在 inorder[4] 的右子樹

因此，可以每次都以 preorder 的第一個元素當 root，然後 recursive 的找出左子樹和右子樹

那當找左右子樹的時候，preorder 的範圍變化會如下

找左子樹時:

preorder[0] 會是當下的 root

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

preorder 不需要再看 index 0，只看 index 1 到 index 5

將 preorder[1-5] 繼續 recursive 下去

preorder : [2, 6, 9, 7, 8]
inorder : [6, 2, 9, 3, 7, 8]

找右子樹時:

preorder[0] 會是當下的 root

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

而這時候，inorder[0-2] 這三個數都是左子樹的元素，且都已經處理完了

所以接下來要看的地方是 inorder[4-5]

這也代表在 preorder 中，從 preorder[0] 往右數 3 個 (inorder[0-2]) 都是處理過的數

所以 preorder 的搜尋範圍起始點就會變成 preorderRootIndex + (inorderRootIndex - inorderStart) + 1 = 0 + (3 - 0) + 1 = 4

也就是從 preorder[4] 開始就會是在右子樹的元素

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>& preorder, vector<int>& inorder) {
	return recursive(0, 0, inorder.size()-1, preorder, inorder);
	}
	TreeNode *recursive(const int &rootPreorderIdx, const int &inStart, const int &inEnd, vector<int>& preorder, vector<int>& inorder) {
	if(inStart > inEnd || rootPreorderIdx == preorder.size()) {
	return NULL;
	}
	TreeNode *root = new TreeNode(preorder[rootPreorderIdx]);
	int rootInorderIdx = inStart;
	while(rootInorderIdx <= inEnd && inorder[rootInorderIdx] != preorder[rootPreorderIdx]) {
	++rootInorderIdx;
	}
	//> left trees
	root->left = recursive(rootPreorderIdx+1, inStart, rootInorderIdx-1, preorder, inorder);
	//> right trees
	root->right = recursive(rootPreorderIdx + (rootInorderIdx - inStart) + 1, rootInorderIdx + 1, inEnd, preorder, inorder);
	return root;
	}
	};

view raw constructBinaryTreeFromPreorderAndInorderTraversal_1.cpp hosted with ❤ by GitHub

這題還有 iterative 的解法

舉例

     1
    / \
   2   7
  / \   \
 6   9   8

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

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

觀念一樣，preorder[0] = 1 一定是 root，所以 inorder[0-2]一定是 root 的左子樹的node

而 inorder[0] = 6，這一定是最左邊的 node

因此，當目前 preorder 的值不等於 inorder[0] 之前，就是一路向左連接下去

     1
    /
   2
  /
 6

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

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

當 preorder[2] = 6 = inorder[0] 的時候，代表目前所有的 left child 都已經處理完了

接下來就要回推到第一個有 right child 的 node

因為要回推，所以在過程當中，使用 stack 將之前的 node 都儲存起來

此實，stack 裡面有 [1, 2, 6]

因為 inorder 的特性，如果有 right child 的 node，其 right child 一定會夾在當前 node 和它的 parent 之間

就像是例子中的 9 : inorder : [6, 2, 9, 1, 7, 8]

因此，只要檢查 stack 裡面的 top，是不是和當前 inorder 的值一樣

是的話，就 pop 出來，然後用一個 tmpNode 指到它，並且將 inorder 的 index 指到下一個

所以會變成

     1
    /
   2
  / \
 6   9

tmpNode = 2

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

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

這時候把 9 變成 2 的 right child，並且再把 9 丟到 stack 就可以了

stack = [1,9]

然後再重複之前的步驟，直到歷遍完 preorder

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>& preorder, vector<int>& inorder) {
	if(preorder.empty()) {
	return NULL;
	}
	int preIdx = 0, inIdx = 0;
	TreeNode *root = new TreeNode(preorder[preIdx++]);
	stack<TreeNode *> nodeStk;
	nodeStk.push(root);
	while(true) {
	//> all the way down to deepest left node
	while(nodeStk.top()->val != inorder[inIdx]) {
	TreeNode *leftNode = new TreeNode(preorder[preIdx++]);
	nodeStk.top()->left = leftNode;
	nodeStk.push(leftNode);
	}
	//> backtrace to the node which has right node
	TreeNode *tmpRootNode;
	while(!nodeStk.empty() && nodeStk.top()->val == inorder[inIdx]) {
	tmpRootNode = nodeStk.top();
	nodeStk.pop();
	++inIdx;
	}
	//> terminate
	if(preIdx == preorder.size()) {
	break;
	}
	//> connect the rifht node
	TreeNode *rightNode = new TreeNode(preorder[preIdx++]);
	tmpRootNode->right = rightNode;
	nodeStk.push(rightNode);
	}
	return root;
	}
	};

view raw constructBinaryTreeFromPreorderAndInorderTraversal_2.cpp hosted with ❤ by GitHub