手机网站申请,安阳实力网站建设首选,优秀企业网站赏析,ASP网站开发步骤与过程前言
前面都是遍历#xff0c;今天是构造二叉树。
前序和中序可以唯一确定一棵二叉树。
后序和中序可以唯一确定一棵二叉树。
前序和后序不能唯一确定一棵二叉树#xff01;
内容
一、从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
给定两个整…前言
前面都是遍历今天是构造二叉树。
前序和中序可以唯一确定一棵二叉树。
后序和中序可以唯一确定一棵二叉树。
前序和后序不能唯一确定一棵二叉树
内容
一、从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。
递归
用哈希表存储中序序列
后序遍历的末尾元素为当前子树的根节点找出它在中序遍历中的位置以此来分割
func buildTree(inorder []int, postorder []int) *TreeNode {hashMap:map[int]int{}for i,v:range inorder{hashMap[v]i}var build func(int,int)*TreeNodebuildfunc(inorderLeft,inordeRight int)*TreeNode{if inorderLeftinordeRight{return nil}val:postorder[len(postorder)-1]postorderpostorder[:len(postorder)-1]root:TreeNode{Val:val}// 由于我们每次都从后序遍历的末尾取元素所以要先遍历右子树再遍历左子树inorderRoot:hashMap[val]root.Rightbuild(inorderRoot1,inordeRight)root.Leftbuild(inorderLeft,inorderRoot-1)return root}return build(0,len(inorder)-1)
}
二、从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder 其中 preorder 是二叉树的先序遍历 inorder 是同一棵树的中序遍历请构造二叉树并返回其根节点。
递归
此时前序遍历的首元素为当前子树的根节点找出它在中序遍历中的位置以此来分割
别忘了要更新前序遍历将用过的首元素去掉
func buildTree(preorder []int, inorder []int) *TreeNode {hashMap:map[int]int{}for i,v:range inorder{hashMap[v]i}var build func(int,int)*TreeNodebuildfunc(inorderLeft,inorderRight int)*TreeNode{if inorderLeftinorderRight{return nil}val:preorder[0]root:TreeNode{Val:val}preorderpreorder[1:]//少了这一步inorderRoot:hashMap[val]root.Leftbuild(inorderLeft,inorderRoot-1)root.Rightbuild(inorderRoot1,inorderRight)return root}return build(0,len(inorder)-1)
}
func buildTree(preorder []int,inorder []int)*TreeNode{if len(preorder)0{return nil}root:TreeNode{preorder[0],nil,nil}i:0for ;ilen(inorder);i{if inorder[i]preorder[0]{break}}root.LeftbuildTree(preorder[1:len(inorder[:i])1],inorder[:i])root.RightbuildTree(preorder[len(inorder[:i])1:],inorder[i1:])return root
}
最后
构造二叉树基础got it
