已解答 中等
相关标签
相关企业给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3] 输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
提示:
- 二叉树的节点个数的范围是
[1,104] -231 <= Node.val <= 231 - 1
func findBottomLeftValue(root *TreeNode) int { var res int var maxDepth int curDepth := 1 var dfs func(node *TreeNode) dfs = func(node *TreeNode) { if node.Left == nil && node.Right == nil { if curDepth > maxDepth { maxDepth = curDepth res = node.Val } } if node.Left != nil { curDepth++ dfs(node.Left) curDepth-- } if node.Right != nil { curDepth++ dfs(node.Right) curDepth-- } } dfs(root) return res } func findBottomLeftValue(root *TreeNode) int { var dfs func(node *TreeNode) (int, int) dfs = func(node *TreeNode) (int, int) { if node.Left == nil && node.Right == nil { return 1, node.Val } var leftHeight, rightHeight, leftVal, rightVal int if node.Left != nil { leftHeight, leftVal = dfs(node.Left) } if node.Right != nil { rightHeight, rightVal = dfs(node.Right) } if leftHeight >= rightHeight { return leftHeight + 1, leftVal } return rightHeight + 1, rightVal } _, res := dfs(root) return res }
func findBottomLeftValueOne(root *TreeNode) int { bfs := []*TreeNode{root} var lastLeft int for len(bfs) > 0 { lastLeft = bfs[0].Val var nbfs []*TreeNode for _, v := range bfs { if v.Left != nil { nbfs = append(nbfs, v.Left) } if v.Right != nil { nbfs = append(nbfs, v.Right) } } bfs = nbfs } return lastLeft }
已解答 中等
相关标签
相关企业给定两个整数数组 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保证是树的后序遍历
func buildTree(inorder []int, postorder []int) *TreeNode { if len(inorder) == 0 { return nil } //找到父结点 pVal := postorder[len(postorder)-1] parent := &TreeNode{Val: pVal} //中序中首结点的位置 var inorderPValPos int for i := 0; i < len(inorder); i++ { if inorder[i] == pVal { inorderPValPos = i break } } leftInorder := inorder[:inorderPValPos] rightInorder := inorder[inorderPValPos+1:] leftPostorder := postorder[:inorderPValPos] rightPostorder := postorder[inorderPValPos : len(postorder)-1] parent.Left = buildTree(leftInorder, leftPostorder) parent.Right = buildTree(rightInorder, rightPostorder) return parent }
已解答 中等
相关标签
相关企业给你二叉树的根节点 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 输出：[]
提示：
- 树中节点总数在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
func pathSum(root *TreeNode, targetSum int) [][]int { var res [][]int if root == nil { return res } trace := []int{root.Val} var dfs func(node *TreeNode, targetSum int) dfs = func(node *TreeNode, targetSum int) { if node.Left == nil && node.Right == nil { if targetSum == 0 { //这里不能直接用trace , 因为数据地址是共享的，需要copy一份 res = append(res, append([]int{}, trace...)) } return } if node.Left != nil { trace = append(trace, node.Left.Val) dfs(node.Left, targetSum-node.Left.Val) trace = trace[:len(trace)-1] } if node.Right != nil { trace = append(trace, node.Right.Val) dfs(node.Right, targetSum-node.Right.Val) trace = trace[:len(trace)-1] } } dfs(root, targetSum-root.Val) return res }
已解答 简单
相关标签
相关企业给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示
func hasPathSum(root *TreeNode, targetSum int) bool { if root == nil { return false } var dfs func(node *TreeNode, targetSum int) bool dfs = func(node *TreeNode, targetSum int) bool { if node.Left == nil && node.Right == nil && targetSum == node.Val { return true } var leftPass, rightPass bool if node.Left != nil { leftPass = dfs(node.Left, targetSum-node.Val) } if node.Right != nil { rightPass = dfs(node.Right, targetSum-node.Val) } return leftPass || rightPass } return dfs(root, targetSum) 标签：node,遍历,nil,int,dfs,二叉树,序列,root,targetSum From： https://www.cnblogs.com/suxinmian/p/18019353