跳到主要内容

由遍历序列构造二叉树

哪些遍历序列组合能唯一确定二叉树？​

组合是否唯一说明
中序 + 前序唯一前序定根, 中序分左右
中序 + 后序唯一后序定根, 中序分左右
中序 + 层序唯一层序定根, 中序分左右
前序 + 后序不唯一度为 1 的节点无法判断子节点方向
单一种序列不唯一缺少切分左右子树的信息

为什么必须包含中序？​

  • 作用: 前序或后序只能确定根节点, 中序用根节点把剩余序列切成左、右两段;
  • 反例: 前序与后序中, 度为 1 的节点在两种序列里的位置无法区分它是左子还是右子;

递归构造的通用步骤是什么？​

  1. 从前序 (或后序) 中取出根节点值;
  2. 在中序里找到根节点的下标 k;
  3. 中序 [0, k) 归左子树, 中序 (k, n) 归右子树;
  4. 按左右子树的节点数切分另一个序列, 对两棵子树递归;

前序 + 中序如何实现？​

const buildTree = function (preorder, inorder) {
  const create = (preorder, inorder, n) => {
    if (n === 0) return null;
    const root = preorder[0];
    const k = inorder.indexOf(root);
    const node = new TreeNode(root);
    node.left = create(preorder.slice(1, k + 1), inorder.slice(0, k), k);
    node.right = create(preorder.slice(k + 1), inorder.slice(k + 1), n - k - 1);
    return node;
  };

  return create(preorder, inorder, preorder.length);
};

中序 + 后序如何实现？​

  • 差异: 根节点在后序末尾; 左子树取 postorder[0, k), 右子树取 postorder[k, n-1);
const buildTree = function (inorder, postorder) {
  const create = (inorder, postorder, n) => {
    if (n === 0) return null;
    const root = postorder[n - 1];
    const k = inorder.indexOf(root);
    const node = new TreeNode(root);
    node.left = create(inorder.slice(0, k), postorder.slice(0, k), k);
    node.right = create(inorder.slice(k + 1), postorder.slice(k, n - 1), n - k - 1);
    return node;
  };

  return create(inorder, postorder, postorder.length);
};

前序 + 后序为何不唯一, 如何构造其中一棵？​

  • 歧义来源: 前序第二个值与后序倒数第二个值可能指向同一个节点, 无法判断它是左子还是右子;
  • 默认口径: 约定前序第二个值就是左子树的根, 据此在后序中定位并切分;
  • 左子树: 前序 [1, k+2), 后序 [0, k+1); 其余部分归右子树;
const constructFromPrePost = function (preorder, postorder) {
  const dfs = (preorder, postorder) => {
    if (preorder.length === 0) return null;
    const root = new TreeNode(preorder[0]);
    if (preorder.length === 1) return root;
    const k = postorder.indexOf(preorder[1]);
    root.left = dfs(preorder.slice(1, k + 2), postorder.slice(0, k + 1));
    root.right = dfs(preorder.slice(k + 2), postorder.slice(k + 1, postorder.length - 1));
    return root;
  };

  return dfs(preorder, postorder);
};

复杂度如何？​

  • 时间: 最坏 O(n^2), 每次递归都用 indexOf 与 slice 扫描区间;
  • 优化: 预处理 "值 → 中序下标" 的哈希表, 可把定位根节点降到 O(1);
  • 空间: O(n), 递归栈与切片产生的临时数组;