跳至主要内容

13.4 前中後序遍歷

前序遍歷、中序遍歷和後序遍歷是三種利用深度優先搜尋（DFS）遍歷二元樹的方式。它們在節點訪問的順序上有所不同，其餘部分完全相同。考慮如下二元樹：

    1
   / \
  2   3
 / \   \
4   5   6

前序遍歷先訪問父節點，再訪問左節點，最後訪問右節點，得到的遍歷順序是 [1 2 4 5 3 6]。

void preorder(TreeNode* root) {
    visit(root);
    preorder(root->left);
    preorder(root->right);
}

中序遍歷先訪問左節點，再訪問父節點，最後訪問右節點，得到的遍歷順序是 [4 2 5 1 3 6]。

void inorder(TreeNode* root) {
    inorder(root->left);
    visit(root);
    inorder(root->right);
}

後序遍歷先訪問左節點，再訪問右節點，最後訪問父節點，得到的遍歷順序是 [4 5 2 6 3 1]。

void postorder(TreeNode* root) {
    postorder(root->left);
    postorder(root->right);
    visit(root);
}

105. Construct Binary Tree from Preorder and Inorder Traversal​

題目描述​

給定一棵二元樹的前序遍歷和中序遍歷結果，嘗試復原這棵樹。已知樹裡不存在重複值的節點。

輸入輸出範例​

輸入是兩個一維陣列，分別表示樹的前序遍歷和中序遍歷結果；輸出是一棵二元樹。

Input: preorder = [4,9,20,15,7], inorder = [9,4,15,20,7]
Output:
    4
   / \
  9  20
     / \
    15  7

題解​

我們通過本題的範例講解一下本題的思路。前序遍歷的第一個節點是 4，意味著 4 是根節點。我們在中序遍歷結果中找到 4 這個節點，根據中序遍歷的性質可以得出：

  • 4 在中序遍歷陣列中的位置左側子陣列為左子樹，節點數為 1，對應的是前序遍歷陣列中 4 之後的 1 個數字（9）。
  • 4 在中序遍歷陣列中的位置右側子陣列為右子樹，節點數為 3，對應的是前序遍歷陣列最後的 3 個數字。

有了這些訊息，我們可以對左子樹和右子樹進行遞迴復原。為了方便查找數字的位置，我們可以用雜湊表預處理中序遍歷的結果。

// 輔助函式。
TreeNode* reconstruct(unordered_map<int, int>& io_map, vector<int>& po, int l,
                      int r, int mid_po) {
    if (l > r) {
        return nullptr;
    }
    int mid_val = po[mid_po];
    int mid_io = io_map[mid_val];
    int left_len = mid_io - l + 1;
    TreeNode* node = new TreeNode(mid_val);
    node->left = reconstruct(io_map, po, l, mid_io - 1, mid_po + 1);
    node->right = reconstruct(io_map, po, mid_io + 1, r, mid_po + left_len);
    return node;
}
// 主函式。
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> io_map;
    for (int i = 0; i < inorder.size(); ++i) {
        io_map[inorder[i]] = i;
    }
    return reconstruct(io_map, preorder, 0, preorder.size() - 1, 0);
}

144. Binary Tree Preorder Traversal​

題目描述​

不使用遞迴，實現二元樹的前序遍歷。

輸入輸出範例​

輸入是一棵二元樹，輸出是一個陣列，表示二元樹前序遍歷的結果。

Input:
    1
     \
      2
     /
    3
Output: [1,2,3]

題解​

由於遞迴的本質是透過堆疊進行函數調用，因此我們可以使用堆疊來實現前序遍歷。注意進堆疊的順序。

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> po;
    if (root == nullptr) {
        return po;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        po.push_back(node->val);
        if (node->right) {
            s.push(node->right);  // 先右後左，保證左子樹先遍歷
        }
        if (node->left) {
            s.push(node->left);
        }
    }
    return po;
}