513. Find Bottom Left Tree Value

Medium

Given the root of a binary tree, return the leftmost value in the last row of the tree.

Example 1:

Input: root = [2,1,3]
Output: 1

Example 2:

Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].

• -2^31 <= Node.val <= 2^31 - 1

解題

Runtime: 0 ms, faster than 100%

Memory Usage: 5.1 MB, less than 100%

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findBottomLeftValue(root *TreeNode) int {
    ans := root.Val
    depth := 0 // 紀錄答案的深度

    var helper func(*TreeNode, int)
    helper = func(node *TreeNode, dep int) {
        if node == nil { return }

        if dep > depth {
            ans = node.Val
            depth = dep
        }

        helper(node.Left, dep + 1) // 每次都先遍歷左邊，答案才會是最左邊的節點
        helper(node.Right, dep + 1)
    }

    helper(root, 0)

    return ans
}