[Leetcode][Medium] 889. Construct Binary Tree from Preorder and Postorder Traversal

文章目錄

• • • • Problem
      • Example
      • Answer
      • Explanation

Problem

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals

pre

and

post

are distinct positive integers.

Example

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]

Output: [1,2,3,4,5,6,7]

Answer

TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) {
      stack<TreeNode*> s;
      s.push(new TreeNode(pre[0]));
        
      for (int i = 1, j = 0; i < pre.size(); ++i) {
          TreeNode* node = new TreeNode(pre[i]);
          while(s.top()->val == post[j]) {
              s.pop();
              j++;
          }
          if (!s.top()->left) s.top()->left = node;
          else s.top()->right = node;
          s.push(node);
      }  
      return s.top();
    }
           

Explanation

感覺這題其實不是太好了解。

首先要對前序周遊和後續周遊比較熟悉

Preorder (Root, Left, Right) 4 2 5 1 3

Postorder (Left, Right, Root) 4 5 2 3 1

如果隻給

pre

是無法完成建樹的，因為不知道某個節點是否是最底部的點。是以

post

給了一個很重要的資訊。

首先維護一個

stack

，裡面存放還沒完成建數的

node

，同時維護一個指針

j

，來檢查

stack

裡面的

node

是否完成建樹。

1. 周遊

   pre

   ，每一個數字都取出來建立新的

   node

2. 取出

   stack

   的最前節點，查詢是否完成建樹

   stack.top() == post[j]

   ，如果完成澤推出

   stack

   。
3. 把建立立的

   node

   設為

   stack

   裡面頭節點的子數，要不然是左 要不然是右（就算隻有一個節點，前序後序輸出都是一樣的）
4. 把新的

   node

   推入

   stack