根据前序遍历和中序遍历还原成后序遍历及相关题目(内部题目很多)golang版本

根据前序遍历和中序遍历还原成后序遍历及相关题目(内部题目很多)golang版本

type TreeNode struct{
	Val int
	Left *TreeNode
	Right *TreeNode
}

//前序遍历
func preorderTraversal(root *TreeNode) []int{
	nums := make([]int,0)
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node != nil{
			nums = append(nums, node.Val)
			dfs(node.Left)
			dfs(dfs.Right)
		}
	}
	dfs(root)
	return nums
}

//中序遍历
func inorderTraversal(root *TreeNode) []int{
	nums := make([]int,0)
	var dfs func(node *TreeNode)
	dfs = func (node *TreeNode)  {
		if node != nil{
			dfs(node.Left)
			nums = append(nums, node.Val)
			dfs(node.Right)
		}
	}
	dfs(root)
	return nums
}

//后序遍历 
func postorderTraversal(root *TreeNode) []int{
	nums := make([]int,0)
	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node != nil{
			dfs(node.Left)
			dfs(node.Right)
			nums = append(nums, node.Val)
		}
	}
	dfs(root)
	return nums
}

//层序遍历
func levelOrder(root *TreeNode) [][]int{
	ret := [][]int{}
	if root == nil{
		return ret
	}

	q = []*TreeNode{root}

	for i :=0;len(q) >0;i++{
		ret = append(ret, []int{})
		p := []*TreeNode{}
		for j :=0;j<len(q);j++{
			node := q[j]
			ret[j] = append(ret[j], node.Val)
			if node.Left != nil{
				p = append(p, node.Left)
			}
			if node.Right != nil{
				p = apppend(p,node.Right)
			}
		}
		q=p
	}
	return ret
}

//层序创建二叉树

func sequenceCreation(nums []int) *TreeNode{
	if len(nums) == 0{
		return nil
	}
	if len(nums) ==1 {
		return &TreeNode{nums[0],nil,nil}
	}
	//先对数组进行分层分割
	sliNums := make([][]int,0)
	count := 1
	for i :=0;i<len(nums);{
		cout := make([]int,0)
		j := i
		for ;j <i+count;j++{
			cont = append(cont,nums[j])
		}
		i = j
		sliNums = append(sliNums,cont)
		count *=2
	}
	root := new(TreeNode)
	root.Val = sliNums[0][0]
	queue := []*TreeNode{root}
	count =0 
	for i :=1;j<len(sliNums);i++{
		for j :=0;j<len(sliNums[i]);j +=2{
			if sliNums[i][j] != -1{
				queue[count].Left = &TreeNode{Val:sliNums[i][j]}
				queue = append(queue,queue[count].Left)
			}else{
				if queue[count] != nil{
					queue[count].Left = nil
					queue = append(queue, queue[count].Left)
				}
			}
			if sliNums[i][j+1] != -1{
				queue[count].Right = &TreeNode{Val: sliNums[i][j+1]}
				queue = append(queue,queue[count].Right)
			}else{
				if queue[count] != nil{
					queue[count].Right = nil
					queue = append(queue,queue[count].Right)
				}
			}
			count++
		}
	}
	return root
}


//二叉树的最大深度
type TreeNode struct{
	Val int
	Left *TreeNode
	Right *TreeNode
}

func max(a,b int) int{
	if a > b {
		return a 
	}
	return b 
}

func maxDepth(root *TreeNode) int{
	if root == nil{
		return 0
	}
	return max(maxDepth(root.Left),maxDepth(root.Right)) + 1
}

//前序中序创建二叉树
type TreeNode1 struct{
	Val int
	Left *TreeNode1
	Right *TreeNode1
}

//前序找根节点，中序找左右分界线
func pBuildTree(preorder []int,inorder []int) *TreeNode{
	if len(preorder) == 0{
		return nil
	}
	root := &TreeNode{preorder[0],nil,nil}
	i := 0
	for i :=0;i<len(inorder);i++{
		if preorder[0] == inorder[i]{
			break
		}
	}
	root.Left = pBuildTree(preorder[1:len(inorder[:i])+1],inorder[:i])
	root.Right = pBuildTree(preorder[len(inorer[:i])+1:],inorder[i+1:])
	return root
}

//中序后序创建二叉树
type TreeNode3 struct{
	Val int
	Left *TreeNode
	Right *TreeNode
}

//从中序后序创建二叉树
func iPBuildTree(inorder []int,postorder []int) *TreeNode{
	idxMap := map[int]int{}
	for i,v := range inorder{
		idxMap[v] = i
	}

	var build func(int, int) *TreeNode

	build = func(inorderLeft , inorderRight int) *TreeNode {
		//无剩余节点
		if inorderLeft > inorderRight{
			return nil
		}
		//后序遍历的末尾元素即为当前子树的根节点
		val := postorder[len(postorder)-1]
		postorder = postorder[:len(postorder)-1]
		root := &TreeNode{Val:val}
		//根据val在中序遍历中的位置，将中序遍历划分成左右两棵子树
		//由于我们每次都从后序遍历的末尾元素，所以要先遍历右子树，再遍历左子树
		inorderRootIndex := idxMap[val]
		root.Right = build(inorderRootIndex+1,inorderRight)
		root.Left = build(inorderLeft,inorderRootIndex-1)
		return root 
	}
	return build(0,len(inorder)-1)
}


//前序后序创建二叉树
type TreeNode struct{
	Val int
	Left *TreeNode
	Right *TreeNode 
}

//根据前序后序构建二叉树
func constructFromPrePost(preorder []int,postorder []int) *TreeNode{
	if len(preorder) == 0{
		return nil
	}
	//如果只有一个元素的时候
	if len(preorder) == 0{
		return &TreeNode{Val:preorder[0],nil,nil}
	}
	//根节点
	root := &TreeNode{Val:preorder[0]}
	//在后序序列中寻找和前序序列根节点下一个节点相等的位置 
	for pos,node := range postorder{
		if node == preorder[1]{
			//构建左子树
			root.Left = constructFromPrePost(preorder[1:pos+2],postorder[:pos+1])
			root.Right = constructFromPrePost(prorder[pos+2:],postorder[pos+1:len(postorder)-1])
			break
		}
	}
	return root
}