题目

leetcode:513

代码与解析

递归

找最左叶子结点,可以使用前序遍历,这样才优先左边搜索,然后同时记录深度最大的叶子节点,此时就是树的最后一行最左边的值。


递归三部曲

  • 确定参数和返回值
    如果在函数内部定义函数的话,可以使用内部变量,而且是遍历整棵树,我这里就传一个参数,就是当前节点。
    如果函数分开定义,那么就要传两个参数。一个当前节点,一个是深度

  • 确定终止条件
    遇到叶子节点终止

if root.Left==nil&&root.Right==nil{
    if maxDepth<tmpDepth{
        maxDepth = tmpDepth
        Value = root.Val
    }
}
  • 确定单层递归逻辑
    这里也要进行回溯
// 中
if root.Left!=nil{  // 左
    tmpDepth++ // 深度加一
    traversal(root.Left)
    tmpDepth-- // 回溯,深度减一
}
if root.Right!=nil{  // 右
    tmpDepth++
    traversal(root.Right)
    tmpDepth--
}
func findBottomLeftValue(root *TreeNode) int {
    // 这里必须判断节点只有根节点的情况。
    if root.Left==nil&&root.Right==nil{
        return root.Val
    }
    maxDepth := 0
    tmpDepth := 0
    Value := 0
    var traversal func(root *TreeNode)
    traversal = func (root *TreeNode){
        if root.Left==nil&&root.Right==nil{
            if maxDepth<tmpDepth{
                maxDepth = tmpDepth
                Value = root.Val
            }
        }
        if root.Left!=nil{
            tmpDepth++
            traversal(root.Left)
            tmpDepth--
        }
        if root.Right!=nil{
            tmpDepth++
            traversal(root.Right)
            tmpDepth--
        }

    }
    traversal(root)
    return Value
}
// 代码简化的话,可以传两个参数,根节点和临时深度,回溯的时候就可以隐藏在函数调用里。

层序遍历

层序遍历的话也可以, 而且更简单,只需要记录每一层的第一个元素

func findBottomLeftValue(root *TreeNode) int {
    // 根节点不为空
    tmp := []int{}
    value := 0
    lis :=list.New()
    lis.PushBack(root)
    for lis.Len()>0{
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            if node.Left!=nil{
                lis.PushBack(node.Left)
            }
            if node.Right !=nil{
                lis.PushBack(node.Right)
            }
            tmp = append(tmp, node.Val)
        }
        value = tmp[0]
        // 清空tmp
        tmp = []int{} //
    }
    return value
}

站点统计

  • 文章总数:315 篇
  • 分类总数:20 个
  • 标签总数:193 个
  • 运行天数:1147 天
  • 访问总数:26695 人次

浙公网安备33011302000604

辽ICP备20003309号