題目:輸入一顆二叉樹和一個整數(shù)邦蜜，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑勇吊。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑.
核心代碼:
<pre><code>`
var path:[String] = []
var listPath:[[String]] = []
func findTreePath(rootNode:TreeNode?,targert:Int)->[[String]]? {
if rootNode == nil {
return nil
}
path.append((rootNode?.data)!)
let value:Int = Int((rootNode?.data)!)!
var temp = targert
temp -= value
if temp == 0 && rootNode?.leftChild == nil && rootNode?.rightChild == nil {
listPath.append(path) // 路徑添加
}
//
if rootNode?.leftChild != nil {// 遞歸遍歷左子樹
_ = findTreePath(rootNode: rootNode?.leftChild, targert: temp)
}
if rootNode?.rightChild != nil { // 遞歸遍歷右子樹
_ = findTreePath(rootNode: rootNode?.rightChild, targert: temp)
}
path.remove(at: path.count-1) // 回溯到父節(jié)點
return listPath
}`</code></pre>
測試代碼:
<pre><code>`
var util:TreeUtil = TreeUtil()
var rootData:[String] = ["10","5","4","#","#","7","#","#","12","#","#"]
var preRootNode:TreeNode?
util.createTreeByPreOrderData(root: &preRootNode, listData: rootData)
var treePath:BinaryTreePath = BinaryTreePath()
var target = 22
var result = treePath.findTreePath(rootNode: preRootNode, targert: target)
print("FlyElephant-和(target)的路徑---(result!)")`</code></pre>
FlyElephant.png
