新农村建设 网站,进出口公司介绍模板,阿里云万网域名注册,wordpress 注册码106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder #xff0c;其中 inorder 是二叉树的中序遍历#xff0c; postorder 是同一棵树的后序遍历#xff0c;请你构造并返回这颗 二叉树 。
//左根右 左右根/*
第一步#xff1a;如果数组大小为零的…
106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder 其中 inorder 是二叉树的中序遍历 postorder 是同一棵树的后序遍历请你构造并返回这颗 二叉树 。
//左根右 左右根/*
第一步如果数组大小为零的话说明是空节点了。
第二步如果不为空那么取后序数组最后一个元素作为节点元素。
第三步找到后序数组最后一个元素在中序数组的位置作为切割点
第四步切割中序数组切成中序左数组和中序右数组 顺序别搞反了一定是先切中序数组
第五步切割后序数组切成后序左数组和后序右数组
第六步递归处理左区间和右区间*/var hash map[int]int
func buildTree(inorder []int, postorder []int) *TreeNode {hash make(map[int]int)for i,v : range inorder{ hash[v] i} root : rebuild(inorder,postorder,len(postorder)-1,0,len(inorder)-1)return root
}func rebuild(inorder []int, postorder []int,rootIdx int,l,r int)*TreeNode{if lr{return nil }if l r {return TreeNode{Val:inorder[l]}}rootV: postorder[rootIdx]root: TreeNode{Val:rootV}rootIn : hash[rootV]root.Left rebuild(inorder,postorder,rootIdx-(r-rootIn)-1,l,rootIn-1)root.Right rebuild(inorder,postorder,rootIdx-1,rootIn1,r)return root
} 112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径这条路径上所有节点值相加等于目标和 targetSum 。如果存在返回 true 否则返回 false 。
叶子节点 是指没有子节点的节点。
func hasPathSum(root *TreeNode,targetSum int) bool{if root nil { return false}if root.Left nil root.Right nil{return root.Val targetSum}return hasPathSum(root.Left,targetSum-root.Val) || hasPathSum(root.Right,targetSum-root.Val)
} 513. 找树左下角的值
给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。 var depth intvar res int
func findBottomLeftValue(root *TreeNode) int {depth,res 0,0 dfs(root,1)return res
}func dfs(root *TreeNode ,d int){if root nil{ return }if root.Left nil root.Right nil depth d{//当前深度大于之前收录的深度depth dres root.Val}dfs(root.Left,d1)dfs(root.Right,d1)
}
