Leetcode 每日抑题 (106. 从中序与后序遍历序列构造二叉树)

本贴最后更新于 1252 天前,其中的信息可能已经渤澥桑田

LeetCode 的每日抑题系列 , LeetCode 会每天随机一道题作为签到题.我也是菜鸡,如果今天没 A 掉,那只能证明我离大神又进了一步.

题目链接

题名 通过率 难度
106. 从中序与后序遍历序列构造二叉树 70.6% 中等

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如,给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

解题思路

递归,不说了,递就完事了.(有人玩怪物猎人嘛,解就完事了.)

根据后序遍历找到根节点,把中序和后序切分成左右子树两部分,递归处理

java 代码

import scala.collection.mutable._

/**
 * 描述:
 * ${DESCRIPTION}
 *
 * @author ludengke
 * @create
 */
object Solution3 extends App {
  def buildTree(inorder: Array[Int], postorder: Array[Int]): TreeNode = {
    buildTree(inorder,0,inorder.length-1,postorder,0,inorder.length-1)
  }

  def buildTree(inOrder: Array[Int], inStart: Int, inEnd: Int, postOrder: Array[Int], postStart: Int, postEnd: Int): TreeNode = {
    if(inEnd < inStart ||postStart > postEnd){
      null
    }else{
      val nodeValue = postOrder(postEnd)
      val index = inOrder.indexOf(nodeValue)
      val node = new TreeNode(nodeValue)
      node.left = buildTree(inOrder,inStart,index - 1,postOrder,postStart,index - 1 - inStart + postStart)
      node.right = buildTree(inOrder,index + 1,inEnd,postOrder,index - inStart + postStart,postEnd - 1)
      node
    }
  }

  val t = buildTree(Array(9,3,15,20,7),Array(9,15,7,20,3))
  println(t)
}



算法 or 数据结构

  1. 递归 , 递归 , 递归
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 递归
    15 引用 • 9 回帖
  • 每日抑题
    6 引用 • 3 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...