代码随想录 day18 第六章二叉树part05

本文主要是介绍代码随想录 day18 第六章二叉树part05，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今日内容

● 513.找树左下角的值

● 112. 路径总和 113.路径总和ii

● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

1. 找树左下角的值

思路
- 递归
  - 最后一行：
    - 找到深度最大的叶子节点，也就找到了最后一行
      - 找到所有叶子节点
        更新值为最新一层第一个出现的叶子节点的值
        最新一层：
        当前最深
        第一个出现的叶子节点
        当前最深一层的最左元素【整个递归遍历，左优先遍历的】
  - 最左边
    - 保证优先左边搜索即可
- 层序
  - 遍历每一层
  - 对当前层的出现的第一个元素更新结果值
    - 当前层的出现的第一个元素：当前最新的左子树
    - 将当前层所有节点的子节点加入下一层的节点中
      - 遍历完当前层所有元素结束
        用一个数组来存储元素，要标记本轮需要遍历的元素个数

题解

递归

func findBottomLeftValue(root *TreeNode) int {if root == nil {return 0}maxDepth, res := 0, 0var traversal func(node *TreeNode, depth int)traversal = func(node *TreeNode, depth int) {//终止条件, 找到叶子节点if node.Left == nil && node.Right == nil { //中//更新最大深度if depth > maxDepth {maxDepth = depthres = node.Val}return}if node.Left != nil { //左//depth++ //进入左孩子，深度+1//traversal(node.Left,depth)//depth-- //回溯，深度--traversal(node.Left, depth+1)}if node.Right != nil { //右//depth++ //进入右孩子，深度+1//traversal(node.Right,depth)//depth-- //回溯，深度--//隐藏回溯traversal(node.Right, depth+1)}}traversal(root, 1) //root的深度记为1return res
}// 简化代码
func findBottomLeftValue(root *TreeNode) int {maxDepth, res := 0, 0var traversal func(node *TreeNode, depth int)traversal = func(node *TreeNode, depth int) {if node == nil {return}//终止条件, 找到叶子节点if node.Left == nil && node.Right == nil && depth > maxDepth { //中//更新最大深度maxDepth = depthres = node.Valreturn}//隐藏回溯//左traversal(node.Left, depth+1)//右traversal(node.Right, depth+1)}traversal(root, 1) //root的深度记为1return res}

迭代【层序遍历，BFS】

func findBottomLeftValue(root *TreeNode) int {if root == nil {return 0}res := 0//深度遍历存储节点nodes := make([]*TreeNode, 0)nodes = append(nodes, root)for len(nodes) > 0 {nodesLen := len(nodes)//当前层//遍历当前层的所有元素, 并将当前层的所有子节点追到到数组中for i := 0; i < nodesLen; i++ {node := nodes[0]//当前层第一个节点nodes = nodes[1:]//弹出节点, 避免重复处理if i == 0 {//当前层第一个节点res = node.Val}if node.Left != nil {nodes = append(nodes, node.Left)}if node.Right != nil{nodes = append(nodes, node.Right)}}}return res
}

2. 路径总和

关联 leetcode 112. 路径总和，和 113. 路径总和ii

思路
- 找到符合要求的一条路径即可
  - 找到一条直接返回
- 递归
  - 直接深度遍历就可以【前中后序都可以】
  - 参数：
    - 根节点【出发点】
    - 计数器，该条路径上的数值总和
      - 如果还没走到叶子就 ≥ 目标值了
        直接回溯
  - 返回值
    - 找到的一条路径即可返回
  - 终止条件
    - 递加的逆向思考
      - 递减
      - 统一结果判断
        如果选用递加还要多比较一次最终值
        只用比较最终结果是否为0即可
    - 找到叶子节点且此时标记递减为0
- 迭代

题解

递归

112. 路径总和

func traversal(node *TreeNode, targetSum int) bool {targetSum -= node.Valif node.Left == nil && node.Right == nil {//已经是叶子节点了return targetSum == 0}if node.Left != nil { //左孩子不为空, 向左递归//递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。if traversal(node.Left, targetSum) {return true}}if node.Right != nil { //右孩子不为空, 向右递归//递归函数是有返回值的，如果递归函数返回true，说明找到了合适的路径，应该立刻返回。if traversal(node.Right, targetSum) {return true}}return false
}
func hasPathSum(root *TreeNode, targetSum int) bool {if root == nil {return false}return traversal(root, targetSum)
}
/* 在函数内实现递归逻辑 */
func hasPathSum(root *TreeNode, targetSum int) bool {if root == nil {return false}targetSum-=root.Valif root.Left == nil && root.Right == nil {//已经是叶子节点了, 只用判断目标值是否刚好扣减到零return targetSum == 0}return hasPathSum(root.Left, targetSum)||hasPathSum(root.Right, targetSum)
}

113. 路径总和ii

思路：路径总和ii要遍历整个树，找到所有路径，所以递归函数不要返回值！

func pathSum(root *TreeNode, targetSum int) [][]int {rets := make([][]int, 0)ret := make([]int, 0)if root == nil {return rets}var traversal func(node *TreeNode, count int)traversal = func(node *TreeNode, count int) {leftNode := node.LeftrightNode := node.Rightif leftNode == nil && rightNode == nil && count == 0 {//这里直接使用 rets = append(rets, ret)//直接使用 rets = append(rets, ret) 会引入一个关键的问题：//由于 Go 语言中的切片（slice）是对底层数组的引用，所以这样直接添加后，//rets 中的所有元素实际上都指向同一个 ret 底层数组。//因此，在后续的回溯过程中，当你修改 ret 时，之前添加到 rets 中的路径也会受到影响。tmp := make([]int, len(ret)) //这里重新声明一个数组来存储结果，与原有ret指向不同底层数组copy(tmp, ret)               //使用copy拷贝切片内容rets = append(rets, tmp)return}if leftNode == nil && rightNode == nil {return}if leftNode != nil { //左, 空节点不遍历leftNodeVal := leftNode.Valret = append(ret, leftNodeVal)traversal(node.Left, count-leftNodeVal)ret = ret[:len(ret)-1] //当前左孩子已经处理过了, 弹出避免重复处理}if rightNode != nil { //右, 空节点不遍历rightNodeVal := rightNode.Valret = append(ret, rightNodeVal)traversal(node.Right, count-rightNodeVal)ret = ret[:len(ret)-1] //当前右孩子已经处理过了, 弹出避免重复处理}}ret = append(ret, root.Val)traversal(root, targetSum-root.Val)return rets
}

迭代
- 二刷再来

3. 从中序与后序遍历序列构造二叉树

关联 leetcode 106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树

本题算是比较难的二叉树题目了，大家先看视频来理解。

106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树一起做，思路一样的

题目链接/文章讲解/视频讲解：https://programmercarl.com/0106.从中序与后序遍历序列构造二叉树.html

思路
- 第一步：如果数组大小为零的话，说明是空节点了。
- 第二步：如果不为空，那么取后序数组最后一个元素作为根节点元素。
- 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
- 第四步：切割中序数组，切成中序左数组和中序右数组（顺序别搞反了，一定是先切中序数组）
- 第五步：切割后序数组，切成后序左数组和后序右数组
- 第六步：递归处理左区间和右区间

题解

106.从中序与后序遍历序列构造二叉树

后面再来优化执行时间

func traversal(inorder []int, postorder []int) *TreeNode {nodesLen := len(inorder)// 第一步：如果数组大小为零的话，说明是空节点了。if nodesLen == 0 {return nil}// 第二步：如果不为空，那么取后序数组最后一个元素作为根节点元素。root := &TreeNode{Val: postorder[nodesLen-1]}if len(inorder) == 1 {return root}// 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点midIdx := 0 // root 在中序中的位置for ; midIdx < nodesLen; midIdx++ {if inorder[midIdx] == root.Val {break}}// 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）leftInorderSons := inorder[:midIdx]rightInorderSons := inorder[midIdx+1:]// 第五步：切割后序数组，切成后序左数组和后序右数组// 题目给出 数组由不同的值组成, 可以直接由节点值本身来切leftLastPostOrderIdx := 0for _, v := range postorder {if !slices.Contains(leftInorderSons, v) {break}leftLastPostOrderIdx++}leftPostorderSons := postorder[:leftLastPostOrderIdx]rightPostorderSons := postorder[leftLastPostOrderIdx : len(postorder)-1] //右孩子, 剔除中间节点// 第六步：递归处理左区间和右区间root.Left = traversal(leftInorderSons, leftPostorderSons)root.Right = traversal(rightInorderSons, rightPostorderSons)return root
}
func buildTree(inorder []int, postorder []int) *TreeNode {return traversal(inorder, postorder)
}

105.从前序与中序遍历序列构造二叉树

// 前序中序中的节点数量一定是一样的
func buildTree(preorder []int, inorder []int) *TreeNode {if len(preorder) == 0 {return nil}// 找到中序的切分索引[根节点在中序中的位置]i := slices.Index(inorder, preorder[0])//左子树的个数: 计数从0开始, i个/*关键在与找到子树的节点个数*/// 切分中序lIn, rIn := inorder[:i], inorder[i+1:]// 切分前序// 剔除掉第一个中间节点, 往后数i个节点数就是 左子树的数量lPre, rPre := preorder[1:i+1], preorder[i+1:]return &TreeNode{Val:   preorder[0],Left:  buildTree(lPre, lIn),Right: buildTree(rPre, rIn),}
}

9. 题外话

构建二叉树
- 前序和后序不能唯一确定一棵二叉树！，因为没有中序遍历无法确定左右部分，也就是无法分割。
- 构建二叉树时
  - 前序、中序只是对当前二叉树的序列排序
  - 包含的节点数量是一致的
递归的处理
- 返回值的选择
  - 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
  - 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。（这种情况我们在**236. 二叉树的最近公共祖先 (opens new window)**中介绍）
  - 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。112.路径总和
- Ali给的建议
  - 在二叉树的深度遍历（DFS，包括前序遍历、中序遍历、后序遍历）中，通常不需要给递归函数设置显式的返回值来获取遍历的结果。因为遍历过程本身可以通过参数传递（如栈、队列或者当前路径等）和全局变量（或闭包变量）来记录遍历结果。
  - 以下是一些情况说明：
    1. 无需返回值：
      - 当我们只需要完成遍历过程，比如打印节点值、更新节点状态等操作，可以直接在递归函数内部处理，无须返回值。
      - 在使用递归遍历时，遍历结果通常是通过传入一个外部变量（例如上述例子中的 rets）来累加和收集的，递归函数本身并不返回最终结果。
    2. 需要返回值：
      - 当我们需要获取特定信息，比如计算某个属性的最值、统计节点数量、查找某个节点是否存在等情况，这时递归函数可能需要返回一个布尔值或者其他类型的结果。
      - 在某些情况下，如果希望递归函数返回一个中间结果（例如在分治算法中），也可能需要返回值。
  - 对于二叉树的深度遍历而言，大部分题目需求不需要递归函数返回值，而是通过参数传递的方式来收集遍历路径或其他信息。当然，具体问题具体分析，根据实际需求决定是否需要返回值。