代码随想录训练营day18 二叉树

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 l>r{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,rootIn+1,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,d+1)dfs(root.Right,d+1)
}