从前序与中序遍历序列构造二叉树-递归

孙泽辉

发布于：2021年8月30日

字数：476字

时长：2分钟

次浏览

做完题之后晕乎乎的，赶紧记下来！

题目

105. 从前序与中序遍历序列构造二叉树

难度中等

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

题解

如何确定一课二叉树呢？

由先序序列的第一个节点可以确定这棵树的根节点。而在中序序列中，该节点将中序序列分为两个子序列，其中一个子序列是根节点的左子树的中序序列，另一个是根节点的右子树的中序序列。根据这两个子序列就可以在先序序列中，划分出根节点的左子树节点的先序节点和右子树节点的先序序列，从这两个先序序列就可以确定左子树的根和右子树的根，用同样的方法可以确定左子树和右子树的其他所有节点。

例如画

先序遍历：3,9,20,15,7 ；后序遍历：9,3,15,20,7

代码实现：

function createTree(
  preorder: number[],
  inorder: number[],
  preStart: number,
  preEnd: number,
  inorStart: number,
  inorEnd: number
): TreeNode | null {
  // Stopping condition
  if (preStart > preEnd || inorEnd < 0) {
    return null;
  }
      
  // preorder 's first is root node.
  const node = new TreeNode();
  node.val = preorder[preStart];

  // split the tree into left and right subtrees.
  // 	find root node position.
  //	go to inorder and find [preorder 's first] element. 
  let inorderRoot = inorStart;
  while (inorderRoot <= inorEnd && preorder[preStart] !== inorder[inorderRoot]) inorderRoot++;
  const rootPos = inorderRoot - inorStart;
  
  // left subtree's preorder = [ preStart, preStart + rootPostion ]
  // left subtree's inorder  = [ inorderStart, inorderRoot - 1 ]
  node.left = createTree(
    preorder,
    inorder,
    preStart + 1,
    preStart + rootPos,
    inorStart,
    inorderRoot - 1
  );
  // right subtree's preorder = [ preStart + rootPostion + 1, preEnd ]
  // right subtree's inorder = [ inorderRoot + 1, inorEnd ]
  node.right = createTree(
    preorder,
    inorder,
    preStart + rootPos + 1,
    preEnd,
    inorderRoot + 1,
    inorEnd
  );
  return node;
}

左右子树的分割位置有一种对称美，不知大家能不能欣赏的出来！