题目

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
}