PigyChan_LeetCode 105. 從前序與中序周遊序列構造二叉樹

105. 從前序與中序周遊序列構造二叉樹

難度中等

根據一棵樹的前序周遊與中序周遊構造二叉樹。

注意:

你可以假設樹中沒有重複的元素。

例如，給出

前序周遊 preorder = [3,9,20,15,7]

中序周遊 inorder = [9,3,15,20,7]

傳回如下的二叉樹：

思路1.0：

(1)周遊前序序列，并在每次周遊時在中序序列中找到目前通路值。

(2)設定隊列，用以輔助我們一層一層地構造二叉樹

思路2.0（已看題解）：

(1)周遊前序序列，并在每次周遊時在中序序列中找到目前通路值的下标mid。

(2)中序序列中，mid左側的所有值構成目前節點的左子樹，左側目前有的元素數量leftLen,

前序序列的右側leftLen個值構成目前節點的左子樹。

(3)中序序列中，mid右側的所有值構成目前節點的右子樹，右側目前有的元素數量rightLen,

前序序列的右側leftLen個值的 右邊leftright個值構成目前節點的右子樹

代碼2.0（以看題解）：

class Solution {
  public:
      int findElement(vector<int> v, int key) {
          auto it=find(v.begin(), v.end(), key);


          if (it != v.end()) {
              return distance(v.begin(), it);
          }
          return -1;
      }


      TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
          if (inorder.size() == 0) return NULL;


          int val = preorder[0];
          TreeNode* TNode = new TreeNode(val);
          auto mid = findElement(inorder, val);


          vector<int> leftPre(preorder.begin() + 1, preorder.begin() + 1 + mid);
          vector<int> leftIn(inorder.begin(), inorder.begin()+mid);
          TNode->left = buildTree(leftPre, leftIn);


          vector<int> rightPre(preorder.begin() + 1 + mid, preorder.end());
          vector<int> rightIn(inorder.begin() + 1 + mid, inorder.end());
          TNode->right = buildTree(rightPre, rightIn);


          return TNode;
      }
  };


           

思路3.0：

遞歸方法的效率有點低，這裡嘗試一下疊代的方法。