257. Binary Tree Paths

Easy

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5]
Output:
 ["1->2->5","1->3"]

Example 2:

Input: root = [1]
Output:
 ["1"]

Constraints:

• The number of nodes in the tree is in the range [1, 100].

• -100 <= Node.val <= 100

解題

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func binaryTreePaths(root *TreeNode) []string {
    if root==nil { return nil }
    
    ans := []string{}
    recursive(root, strconv.Itoa(root.Val), &ans)
    
    return ans
}

func recursive(root *TreeNode, str string, ans *[]string) {
    if root.Left==nil && root.Right==nil {
        *ans = append(*ans, str)
    }
    
    if root.Left!=nil {
        recursive(root.Left, str+"->"+strconv.Itoa(root.Left.Val), ans)
    }
    if root.Right!=nil {
        recursive(root.Right, str+"->"+strconv.Itoa(root.Right.Val), ans)
    }
}

或是下面這個寫法，和上面邏輯完全相同，但是將recursive function 寫成函式內的變數，比較漂亮且不需要傳遞指針。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func binaryTreePaths(root *TreeNode) []string {
    if root==nil { return nil }
    
    ans := []string{}
    
    var recursive func(*TreeNode, string) 
    recursive = func(root *TreeNode, str string) {
        if root.Left==nil && root.Right==nil {
            ans = append(ans, str)
        }
        
        if root.Left!=nil {
            recursive(root.Left, str+"->"+strconv.Itoa(root.Left.Val))
        }
        
        if root.Right!=nil {
            recursive(root.Right, str+"->"+strconv.Itoa(root.Right.Val))
        }
    }
    
    recursive(root, strconv.Itoa(root.Val))
    
    return ans
}