题目：
513. 找树左下角的值
已解答
中等
相关标签
相关企业
给定一个二叉树的 根节点
root，请找出该二叉树的 最底层 最左边 节点的值。假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
思路：
1.本地采用迭代法的层序遍历会比较简单，每层存入二维数组队列，返回最后一层的第一个元素即可
算法：
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func findBottomLeftValue(root *TreeNode) int {//层序遍历，返回最后一层的第一个元素即可arr := make([][]int, 0)if root == nil {return 0} tmp := make([]int,0)que := list.New()que.PushBack(root)for que.Len() != 0 {size := que.Len()for i := 0; i < size; i++ {node := que.Remove(que.Front()).(*TreeNode)if node.Left != nil {que.PushBack(node.Left)}if node.Right != nil {que.PushBack(node.Right)}tmp = append(tmp, node.Val)}arr = append(arr,tmp)tmp = []int{}}return arr[len(arr)-1][0]
}注意：
题目：
112. 路径总和
给你二叉树的根节点
root和一个表示目标和的整数targetSum。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。提示：
- 树中节点的数目在范围
[0, 5000]内-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
思路：
1.递归法，判断叶子节点
2.若是叶子节点，判断是否targetnum-val==0，符合则返回true
3.本题不需要遍历完所有节点
算法：
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func hasPathSum(root *TreeNode, targetSum int) bool {if root == nil {return false}//终止条件if root.Left == nil && root.Right == nil && targetSum - root.Val == 0 {return true}if root.Left == nil && root.Right == nil {return false}return hasPathSum(root.Left, targetSum - root.Val) || hasPathSum(root.Right, targetSum - root.Val)
}注意：
题目：
113. 路径总和 II
给你二叉树的根节点
root和一个整数目标和targetSum，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]示例 3：
输入：root = [1,2], targetSum = 0 输出：[]
思路：
算法：
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func pathSum(root *TreeNode, targetSum int) (ans [][]int) {path := []int{}var dfs func(*TreeNode, int)dfs = func(node *TreeNode, left int){if node == nil {return}left -= node.Valpath = append(path, node.Val)defer func() {path = path[:len(path)-1]}()if node.Left == nil && node.Right == nil && left == 0 {ans = append(ans,append([]int(nil), path...) )return}dfs(node.Left, left)dfs(node.Right, left)}dfs(root, targetSum)return
}注意：
题目：
106. 从中序与后序遍历序列构造二叉树
给定两个整数数组
inorder和postorder，其中inorder是二叉树的中序遍历，postorder是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]示例 2:
输入：inorder = [-1], postorder = [-1] 输出：[-1]提示:
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder和postorder都由 不同 的值组成postorder中每一个值都在inorder中inorder保证是树的中序遍历postorder保证是树的后序遍历
思路：
算法：
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
var hash map[int]int
func buildTree(inorder []int, postorder []int) *TreeNode {hash = make(map[int]int,0)for i, v := range inorder {hash[v] = i}root := rebuild(inorder, postorder, len(postorder)-1, 0, len(inorder)-1)return root}//rootIdx表示根节点在后序数组中的索引，l, r 表示在中序数组中的前后切分点
func rebuild(inorder []int, postorder []int, rootIdx, l, r int) *TreeNode {if l > r {return nil // 说明没有元素，返回空树}if l == r {// 只剩唯一一个元素，直接返回return &TreeNode{Val:inorder[l]} }rootV := postorder[rootIdx] // 根据后序数组找到根节点的值rootIn := hash[rootV]root := &TreeNode{Val : 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
}
