Go 刷 leetcode｜從前序與中序遍歷序列構(gòu)造二叉樹

今天為大家講解 LeetCode 第 105 題，是一道關(guān)于數(shù)組和樹的題目。

題目描述

根據(jù)一棵樹的前序遍歷與中序遍歷構(gòu)造二叉樹。

注意: 你可以假設(shè)樹中沒有重復(fù)的元素。

例如，給出

前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7] 返回如下的二叉樹：

    3
   / \
  9  20
    /  \
   15   7
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路

preorder第一個元素為root，在inorder里面找到root，在它之前的為左子樹（長stopIndex），之后為右子樹。preorder[1]到preorder[stopIndex]為左子樹,之后為右子樹，分別遞歸。

代碼實現(xiàn)

//go
/**
?*?Definition?for?a?binary?tree?node.
?*?type?TreeNode?struct?{
?*?????Val?int
?*?????Left?*TreeNode
?*?????Right?*TreeNode
?*?}
?*/
func?buildTree(preorder?[]int,?inorder?[]int)?*TreeNode?{
????if?len(preorder)?==?0?{
????????return?nil
????}
????root?:=?&TreeNode{preorder[0],?nil,?nil}
????i?:=?0
????//?在inorder里root的下標(biāo)
????for?;?i?len(inorder);?i++?{
????????if?inorder[i]?==?preorder[0]?{
????????????break
????????}
????}
????//?root前的長度，即左子樹的長度
????stopIndex?:=?len(inorder[:i])+1
????root.Left?=?buildTree(preorder[1:stopIndex],?inorder[:i])
????root.Right?=?buildTree(preorder[stopIndex:],?inorder[i+1:])
????return?root
}

鄭重聲明：

所展示代碼已通過 LeetCode 運行通過，請放心食用～