重建二叉树

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

例如:

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

得到如下二叉树:

   3
   / \
  9  20
    /  \
   15   7



解法:递归算法

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
let buildTree = function(preorder, inorder) {
  if (!preorder.length || !inorder.length) return null;
  // 前序遍历的第一个元素为根节点
  let root = new TreeNode(preorder[0]);
  // 获取根节点在中序遍历中的位置(用于分割左右子树)
  let index = inorder.indexOf(preorder[0]);
  // 递归
  root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index));
  root.right = buildTree(preorder.slice(index + 1), inorder.slice(index + 1));
  return root;
};


评论(0)

评论