莺时

东边日出西边雨,道是无晴却有晴

Open Source, Open Mind,
Open Sight, Open Future!
  menu
18 文章
3692 浏览
0 当前访客
ღゝ◡╹)ノ❤️

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

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

题目链接

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

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

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

例如,给出

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

解题思路

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

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

java代码

 1import scala.collection.mutable._
 2
 3/**
 4 * 描述:
 5 * ${DESCRIPTION}
 6 *
 7 * @author ludengke
 8 * @create
 9 */
10object Solution3 extends App {
11  def buildTree(inorder: Array[Int], postorder: Array[Int]): TreeNode = {
12    buildTree(inorder,0,inorder.length-1,postorder,0,inorder.length-1)
13  }
14
15  def buildTree(inOrder: Array[Int], inStart: Int, inEnd: Int, postOrder: Array[Int], postStart: Int, postEnd: Int): TreeNode = {
16    if(inEnd < inStart ||postStart > postEnd){
17      null
18    }else{
19      val nodeValue = postOrder(postEnd)
20      val index = inOrder.indexOf(nodeValue)
21      val node = new TreeNode(nodeValue)
22      node.left = buildTree(inOrder,inStart,index - 1,postOrder,postStart,index - 1 - inStart + postStart)
23      node.right = buildTree(inOrder,index + 1,inEnd,postOrder,index - inStart + postStart,postEnd - 1)
24      node
25    }
26  }
27
28  val t = buildTree(Array(9,3,15,20,7),Array(9,15,7,20,3))
29  println(t)
30}
31
32
33

算法or数据结构

  1. 递归 , 递归 , 递归

标题:Leetcode 每日抑题 (106. 从中序与后序遍历序列构造二叉树)
作者:ludengke95
地址:http://xvhi.ludengke95.xyz/articles/2020/09/25/1601031474492.html