題目

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

解題思路

使用遞歸解題，遞歸的過程中記錄當(dāng)前的路徑，找到葉子節(jié)點后將路徑放入結(jié)果數(shù)組中，在遞歸過程中：

1. 如果左右子節(jié)點都為空指針，則說明當(dāng)前節(jié)點為二叉樹的葉子，獲得一條路徑，將這條路徑加入結(jié)果數(shù)組中
2. 否則分別判斷左右子節(jié)點是否為空，如果不為空，則進行遞歸繼續(xù)尋找其路徑

代碼

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var ret []string

func getPath(t *TreeNode, s string)  {
    val := t.Val
    s = s + "->" + strconv.Itoa(val)
    
    if nil == t.Left && nil == t.Right {
        ret = append(ret, s)
    }
    if nil != t.Left {
        getPath(t.Left, s)
    }
    if nil != t.Right {
        getPath(t.Right, s)
    }
}

func binaryTreePaths(root *TreeNode) []string {
    ret = []string{}
    if nil == root {
        return ret
    }

    rootval := root.Val
    
    if nil == root.Left && nil == root.Right {
        ret = append(ret, strconv.Itoa(rootval))
        return ret 
    } 
    if nil != root.Left {
        getPath(root.Left, strconv.Itoa(rootval))
    } 
    if nil != root.Right {
        getPath(root.Right, strconv.Itoa(rootval))
    }
    

    return ret
}