根据前序和后序遍历构造二叉树 图解题解

两个数组要还原成同一棵树

给你同一棵二叉树的前序遍历数组 preorder 和后序遍历数组 postorder，值互不相同，请把这棵树搭出来，前序开头就是整棵树的根。题面给的 preorder=[50,30,20,40,80,60,90]、postorder=[20,40,30,60,90,80,50]，还原后按层序，也就是一层层横着读，是 50、30、80、20、40、60、90。一份输入可能对应好几棵树，返回任意一棵都算对。

光有前序，左右子树切在哪儿

假设手里只有前序。根是开头那个数，可根后面一长串里，前一段属于左子树、后一段属于右子树，中间那条分界线前序自己并不标出来。想还原只能挨个位置去假设「左子树占 k 个」，切开往下建，建不成再退回来换个 k，一棵 n 个节点的树试下来是指数级的功夫。若给的是前序加中序，中序能把根左右两边天然隔开，可这题给的是后序，得换个地方找分界线。

后序结尾框定左子树的大小

转机在后序。前序里根紧后面那个数 preorder[a+1]，就是左子树自己的根（前提是它有左子树）。后序会把一整棵左子树排在连续的一段里，左子树的根恰好落在这段的最末。拿 preorder[a+1] 去后序里查它排第几位，从段首数到它就是左子树的节点数，右边剩下的全归右子树。每次现扫后序是 O(n)、整体滑到 O(n²)；先把后序每个值映射到下标存进哈希表 pos，查位置只要 O(1)。

每一段递归各自建好一棵子树

写成一个递归 dfs，它盯着前序的一个区间和后序的一个区间，这两段是同一棵子树的两种排法。区间空了返回空；只剩一个数就是叶子，直接建好返回、不再往下取。否则拿前序开头 preorder[a] 建根，用 preorder[a+1] 在后序里的位置算出左子树大小 m。左子树递归前序接下来的 m 个配后序对应段，右子树递归前序剩下的配后序去掉末尾根的一段。孩子建好挂到根下，返回这个根。

拿题面这棵 7 节点树切一遍

回到题面这棵树。前序开头 50 是根，后面的 30 是左子树的根；30 在后序里排第 3 个（前面是 20、40），左子树占 3 个节点，前序后序据此各切成左右两半递归。左段根 30，20 在后序里排第 1 个、左子树只 1 个，于是 20 当左孩子、40 当右孩子，都成叶子返回。右段同理，根 80、左孩子 60、右孩子 90。全挂回去，读出的层序 50、30、80、20、40、60、90 正是题面要的那棵树。

少加一个 1，整段就会错位

最容易栽的是把左子树大小算成后序位置减区间起点、忘了加 1——位置差要加 1 才是元素个数，少算一个左右边界就整体挪位、往下全建歪。区间只剩一个数时别急着取 preorder[a+1]：那时它本就是叶子，硬取要么下标越界，要么把叶子误当成还带着左子树。前序加后序还定不出唯一的树——某节点只有一个孩子时挂左挂右两份序列一模一样、分不出来，题目才允许返回任意一种。时间上每个节点只建一次、查位置靠哈希表 O(1)，合计 O(n)；空间是哈希表加递归栈 O(n)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructFromPrePost(
        self, preorder: List[int], postorder: List[int]
    ) -> Optional[TreeNode]:
        def dfs(a: int, b: int, c: int, d: int) -> Optional[TreeNode]:
            if a > b:
                return None
            root = TreeNode(preorder[a])
            if a == b:
                return root
            i = pos[preorder[a + 1]]
            m = i - c + 1
            root.left = dfs(a + 1, a + m, c, i)
            root.right = dfs(a + m + 1, b, i + 1, d - 1)
            return root

        pos = {x: i for i, x in enumerate(postorder)}
        return dfs(0, len(preorder) - 1, 0, len(postorder) - 1)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        unordered_map<int, int> pos;
        int n = postorder.size();
        for (int i = 0; i < n; ++i) {
            pos[postorder[i]] = i;
        }
        function<TreeNode*(int, int, int, int)> dfs = [&](int a, int b, int c, int d) -> TreeNode* {
            if (a > b) {
                return nullptr;
            }
            TreeNode* root = new TreeNode(preorder[a]);
            if (a == b) {
                return root;
            }
            int i = pos[preorder[a + 1]];
            int m = i - c + 1;
            root->left = dfs(a + 1, a + m, c, i);
            root->right = dfs(a + m + 1, b, i + 1, d - 1);
            return root;
        };
        return dfs(0, n - 1, 0, n - 1);
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private Map<Integer, Integer> pos = new HashMap<>();
    private int[] preorder;

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        this.preorder = preorder;
        for (int i = 0; i < postorder.length; ++i) {
            pos.put(postorder[i], i);
        }
        return dfs(0, preorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode dfs(int a, int b, int c, int d) {
        if (a > b) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[a]);
        if (a == b) {
            return root;
        }
        int i = pos.get(preorder[a + 1]);
        int m = i - c + 1;
        root.left = dfs(a + 1, a + m, c, i);
        root.right = dfs(a + m + 1, b, i + 1, d - 1);
        return root;
    }
}