重建二叉树

重建二叉树：二叉树分成三种遍历方式，给定其中两个遍历方式的结果，然后重建二叉树的过程（或者求另一个遍历方式结果）。

题目1-二叉树重建

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路

• 前序遍历：根节点 + 左子树 + 右子树
• 中序遍历：左子树 + 根节点 + 右字数
• 后序遍历：左子树 + 右子树 + 根节点

根据上面的规律：

• 找到根结点root
• 找到root在中序遍历的位置 -> 获取左子树的长度，右子树的长度
• 截取左子树的中序遍历、右子树的中序遍历
• 截取左子树的前序遍历、右子树的前序遍历
• 递归重建二叉树

代码

/**
 * rebuild binary tree from preorder traversal adn inorder traversal
 * @param {string} pre preorder result
 * @param {string} mid inorder result
 * @returns {TreeNode} binary tree
 */
const rebuildBinaryTree = function (pre, mid) {
  if (pre.length == 0) {
    return null;
  }
  const rootVal = pre[0];
  const node = new TreeNode(rootVal);
  if (pre.length == 1) {
    return node;
  }
  const index = mid.indexOf(rootVal);
  const midLeft = mid.slice(0, index);
  const midRight = mid.slice(index + 1);
  const preLeft = pre.slice(1, index + 1);
  const preRight = pre.slice(index + 1);
  node.left = rebuildBinaryTree(preLeft, midLeft);
  node.right = rebuildBinaryTree(preRight, midRight);
  return node;
};

题目2-求二叉树的后序遍历

给定一棵二叉树的前序遍历和中序遍历，求其后序遍历

输入描述:

两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

输出描述:

输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。

样例1：

输入
ABC
BAC


输出
BCA

样例2：

输入
FDXEAG
XDEFAG

输出
XEDGAF

思路

和上面题目的思路基本相同

• 前序遍历找到根结点root
• 找到root在中序遍历的位置 -> 左子树的长度和右子树的长度
• 截取左子树的中序遍历、右子树的中序遍历
• 截取左子树的前序遍历、右子树的前序遍历
• 递归拼接二叉树的后序遍历

代码

function getBinaryTreePostOrder(pre, mid) {
  if (!pre) {
    return '';
  }
  if (pre.length === 1) {
    return pre;
  }
  const head = pre[0];
  const index = mid.indexOf(head);
  const midLeft = mid.substring(0, index);
  const midRight = mid.substring(index + 1);
  const preLeft = pre.substring(1, index + 1);
  const preRight = pre.substring(index + 1);
  return getBinaryTreePostOrder(preLeft, midLeft) + getBinaryTreePostOrder(preRight, midRight) + head;
}

---

Last update: November 5, 2023