?
Given preorder and inorder 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 Inorder and Postorder Traversal 由中序和后序遍歷建立二叉樹原理基本相同，針對這道題，由于先序的順序的第一個肯定是根，所以原二叉樹的根節點可以知道，題目中給了一個很關鍵的條件就是樹中沒有相同元素，有了這個條件我們就可以在中序遍歷中也定位出根節點的位置，并以根節點的位置將中序遍歷拆分為左右兩個部分，分別對其遞歸調用原函數。代碼如下：
?
/*** Definition for binary tree* 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 buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);}TreeNode *buildTree(vector<int> &preorder, int pLeft, int pRight, vector<int> &inorder, int iLeft, int iRight) {if (pLeft > pRight || iLeft > iRight) return NULL;int i = 0;for (i = iLeft; i <= iRight; ++i) {if (preorder[pLeft] == inorder[i]) break;}TreeNode *cur = new TreeNode(preorder[pLeft]);cur->left = buildTree(preorder, pLeft + 1, pLeft + i - iLeft, inorder, iLeft, i - 1);cur->right = buildTree(preorder, pLeft + i - iLeft + 1, pRight, inorder, i + 1, iRight);return cur;} };
?
我們下面來看一個例子, 某一二叉樹的中序和后序遍歷分別為：
Preorder: ? 5 4 11 8 13 9
LEETCODE，Inorder: 11 4 5 13 8 9
?
5 4 11 8 13 9 => 5
11 4 5 13 8 9 / \
?
hand、4 11 8 ?13 9 => 5
11 4 13 8 9 ? / \
4 8
?
11 13 9 => 5
leetcode 第一題？11 ?13 9 ? / \
4 8
/ /???? \
11 ? 13 ? 9
?
leetcode并查集。做完這道題后，大多人可能會有個疑問，怎么沒有由先序和后序遍歷建立二叉樹呢，這是因為先序和后序遍歷不能唯一的確定一個二叉樹，比如下面五棵樹：
? ? 1 preorder: ?1 2 3
? ?/ \ ?inorder: ? ? 2 1 3
?2 ? ?3 ? postorder: 2 3 1
?
? ? ? ?1 ?? preorder: ? 1 2 3
? ? ? / inorder: ? ? 3 2 1
? ? 2 ??? postorder:? 3 2 1
? ?/
?3
?
leetcode java？? ? ? ?1 ? ?preorder: ?1 2 3
? ? ? / ?inorder: ? ?2 3 1
? ? 2 postorder: 3 2 1
? ? ? \
? ? ? ?3
?
? ? ? ?1 ? ??preorder: ?1 2 3
? ? ? ? ?\ ? inorder: ? ?1 3 2
? ? ? ? ? 2 postorder: 3 2 1
? ? ? ? ?/
? ? ? ?3
?
? ? ? ?1 ? ? preorder: ?1 2 3
? ? ? ? ?\ inorder: ? ?1 2 3
? ? ? ? ? 2 postorder: 3 2 1
? ? ? ? ? ? \
3
?
?從上面我們可以看出，對于先序遍歷都為1 2 3的五棵二叉樹，它們的中序遍歷都不相同，而它們的后序遍歷卻有相同的，所以只有和中序遍歷一起才能唯一的確定一棵二叉樹。
?
LeetCode All in One 題目講解匯總(持續更新中...)
?
