遍历序列怎样构造二叉树

今天就跟大家聊聊有关遍历序列怎样构造二叉树，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

成都创新互联公司坚持“要么做到，要么别承诺”的工作理念，服务领域包括：网站制作、成都网站建设、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的科尔沁网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

算法：

该类题目的核心在于利用前序或者后序遍历找到根节点，利用中序遍历分成左右两棵子树，然后递归操作即可。

前序遍历：根节点，左子树，右子树中序遍历：左子树，根节点，右子树后序遍历：左子树，右子树，根节点前序/后序先找到根节点，利用两种遍历场景的左/右子树的长度相同，找到中序的左右子树

题目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}

执行结果：

看完上述内容，你们对遍历序列怎样构造二叉树有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注创新互联行业资讯频道，感谢大家的支持。

本文题目：遍历序列怎样构造二叉树
本文URL：https://www.cdcxhl.com/article44/ggocee.html

成都网站建设公司_创新互联，为您提供关键词优化、静态网站、网站营销、Google、外贸网站建设、建站公司

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联