根据前序遍历结果和中序遍历结果创建树
思路
由于前序遍历先访问根节点,故前序遍历数组的第0号元素一定为整棵树的根节点
由于中序遍历先访问左子树,后访问根。故中序遍历数组以根为中点左为左子树右为右子树
JavaScript代码
根据后序遍历和中序遍历结果创建树
思路
由于后序遍历先左子树后右子树,故其结果数组的最后一个一定是整棵树的根节点
结合中序遍历可以确定出左子树和右子树的范围
JavaScript代码
实现二
根据中序遍历结果创建一颗平衡搜索二叉树
思路
中序遍历结果一定是一个按升序排列的有序数组
如果一棵树是平衡树,则中序遍历产生的数组中,整棵树的根节点一定在靠近数组中间的位置。以该位置为分割,左侧的节点数与右侧相等或超出(少于)一个
JavaScript代码