[Swift]LeetCode257.二叉树的所有路径|BinaryTreePaths

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9749685.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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

Note: A leaf is a node with no children.

Example:

Input:

   1
 /   \
2     3
 \
  5

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

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

16ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func binaryTreePaths(_ root: TreeNode?) -> [String] {
16         var list:[String] = [String]()
17         recuesive(root,&list,String())
18         return list
19     }
20     func recuesive(_ root:TreeNode?,_ list:inout [String],_ str:String)
21     {
22         if root == nil {return}
23         var strNew:String = str
24         var strRoot:String = String(root!.val)
25         if root?.left == nil && root?.right == nil
26         {
27             strNew = strNew + strRoot
28             list.append(strNew)
29             return
30         }
31         strRoot = strNew + strRoot + "->"
32         recuesive(root?.left,&list,strRoot)
33         recuesive(root?.right,&list,strRoot)
34     }
35 }

16ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func binaryTreePaths(_ root: TreeNode?) -> [String] {
16         guard let root = root else {
17             return []
18         }
19         var result = [String]()
20         binaryTreePathsDFS(root, "", &result)
21         return result
22     }
23     
24     func binaryTreePathsDFS(_ root: TreeNode, _ out: String, _ result: inout [String]) {
25         if root.left == nil && root.right == nil {
26             result.append(out + String(root.val))
27         }
28         
29         if root.left != nil {
30             binaryTreePathsDFS(root.left!, out + String(root.val) + "->", &result)
31         }
32         if root.right != nil {
33             binaryTreePathsDFS(root.right!, out + String(root.val) + "->", &result)
34         }
35         
36     }
37 }

16ms

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     public var val: Int
 5  *     public var left: TreeNode?
 6  *     public var right: TreeNode?
 7  *     public init(_ val: Int) {
 8  *         self.val = val
 9  *         self.left = nil
10  *         self.right = nil
11  *     }
12  * }
13  */
14 class Solution {
15     func binaryTreePaths(_ root: TreeNode?) -> [String] {
16         var ans = [String]()
17         binaryTreePaths(root, "", &ans)
18         return ans
19     }
20     
21     func binaryTreePaths(_ node: TreeNode?, _ path: String, _ ans: inout [String]) {
22         guard let node = node else { return }
23         
24         let path = path + String(node.val)
25         
26         if node.left == nil && node.right == nil {
27             ans.append(path)
28             return 
29         }
30         
31         binaryTreePaths(node.left, path + "->", &ans)
32         binaryTreePaths(node.right, path + "->", &ans)
33     }
34 }