溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
今天就跟大家聊聊有關(guān)遍歷序列怎樣構(gòu)造二叉樹，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。
算法：
該類題目的核心在于利用前序或者后序遍歷找到根節(jié)點，利用中序遍歷分成左右兩棵子樹，然后遞歸操作即可。
前序遍歷：根節(jié)點，左子樹，右子樹中序遍歷：左子樹，根節(jié)點，右子樹后序遍歷：左子樹，右子樹，根節(jié)點前序/后序先找到根節(jié)點，利用兩種遍歷場景的左/右子樹的長度相同，找到中序的左右子樹
題目1: 前序和中序構(gòu)造二叉樹
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
代碼實現(xiàn)：
/** * 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 := new(TreeNode) root.Val = preorder[0] var i int for i<len(inorder) { if preorder[0] == inorder[i] { // 記錄中序遍歷中的父親節(jié)點位置 break } i++ } l := len(inorder[:i]) // 同一個棵樹的長度相同 root.Left = buildTree(preorder[1:l+1],inorder[:i]) root.Right = buildTree(preorder[l+1:],inorder[i+1:]) return root}// 算法：// 前序遍歷：根節(jié)點，左子樹，右子樹// 中序遍歷：左子樹，根節(jié)點，右子樹// 中序先找到根節(jié)點，利用兩種遍歷場景的左/右子樹的長度相同，找到中序的左右子樹
執(zhí)行結(jié)果：
題目2:中序和后續(xù)構(gòu)造二叉樹
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
代碼實現(xiàn)：
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func buildTree(inorder []int, postorder []int) *TreeNode { if len(inorder) == 0 { return nil } l := len(postorder) root := &TreeNode{Val:postorder[l-1]} i:=0 for i<len(inorder) { if inorder[i] == root.Val { break } i++ } root.Left = buildTree(inorder[:i],postorder[:len(inorder[:i])]) root.Right = buildTree(inorder[i+1:],postorder[len(inorder[:i]):l-1]) return root}
執(zhí)行結(jié)果：
看完上述內(nèi)容，你們對遍歷序列怎樣構(gòu)造二叉樹有進(jìn)一步的了解嗎？如果還想了解更多知識或者相關(guān)內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼