您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
今天就跟大家聊聊有关遍历序列怎样构造二叉树，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。
算法：
该类题目的核心在于利用前序或者后序遍历找到根节点，利用中序遍历分成左右两棵子树，然后递归操作即可。
前序遍历：根节点，左子树，右子树中序遍历：左子树，根节点，右子树后序遍历：左子树，右子树，根节点前序/后序先找到根节点，利用两种遍历场景的左/右子树的长度相同，找到中序的左右子树
题目1: 前序和中序构造二叉树
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
代码实现：
/** * 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] { // 记录中序遍历中的父亲节点位置 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}// 算法：// 前序遍历：根节点，左子树，右子树// 中序遍历：左子树，根节点，右子树// 中序先找到根节点，利用两种遍历场景的左/右子树的长度相同，找到中序的左右子树
执行结果：
题目2:中序和后续构造二叉树
https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
代码实现：
/** * 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}
执行结果：
看完上述内容，你们对遍历序列怎样构造二叉树有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注亿速云行业资讯频道，感谢大家的支持。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。