剑指Offer - 4 - 重建二叉树

题目描述

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路

1. 前序遍历第一个节点必是根节点
2. 中序遍历根节点左边的节点必在左子树上，右边的节点必在右子树上
3. 利用递归构建树

Code

• Python

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
      if len(pre) == 0:
        return None
      root = pre[0]
      node = TreeNode(root)
      l = len(pre)
      idx = tin.index(root)
      
      vleft = tin[0:idx]
      vright = tin[idx+1:l]

      pleft = pre[1:idx+1]
      pright = pre[idx+1:l]
      
      node.left = self.reConstructBinaryTree(pleft, vleft)
      node.right = self.reConstructBinaryTree(pright, vright)
      
      return node

• JavaScript

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
  if (pre.length === 0) return undefined
  const len = pre.length
  const root = pre[0]
  const node = new TreeNode(root)
  const idx = vin.indexOf(root)
  
  const vleft = vin.slice(0, idx)
  const vright = vin.slice(idx + 1, len)
  
  const pleft = pre.slice(1, idx + 1)
  const pright = pre.slice(idx + 1, len)
  
  node.left = reConstructBinaryTree(pleft, vleft)
  node.right = reConstructBinaryTree(pright, vright)
  return node
}