[Swift]LeetCode1028. 从先序遍历还原二叉树 | Recover a Tree F

发布时间：2020-12-14 04:53:49 所属栏目：百科来源：网络整理

导读：We run a?preorder?depth first search on the? root ?of a binary tree. At each node in this traversal,we output? D ?dashes (where? D ?is the? depth ?of this node),then we output the value of this node.?? (If the depth of a node is? D ,the de

We run a?preorder?depth first search on the?root?of a binary tree.

At each node in this traversal,we output?D?dashes (where?D?is the?depth?of this node),then we output the value of this node.??(If the depth of a node is?D,the depth of its immediate child is?D+1.? The depth of the root node is?0.)

If a node has only one child,that child is guaranteed to be the left child.

Given the output?S?of this traversal,recover the tree and return its?root.

Example 1:

Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Example 2:

Input: "1-2--3---4-5--6---7"
Output: [1,null,7]

Example 3:

Input: "1-401--349---90--88"
Output: [1,401,349,88,90]

Note:

The number of nodes in the original tree is between?1?and?1000.?
Each node will have a value between?1?and?10^9.

我们从二叉树的根节点?root?开始进行深度优先搜索。

在遍历中的每个节点处，我们输出?D?条短划线（其中?D?是该节点的深度），然后输出该节点的值。（如果节点的深度为?D，则其直接子节点的深度为?D + 1。根节点的深度为?0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出?S，还原树并返回其根节点?root。

示例 1：

输入："1-2--3--4-5--6--7"
输出：[1,7]

示例 2：

输入："1-2--3---4-5--6---7"
输出：[1,7]

示例 3：

输入："1-401--349---90--88"
输出：[1,90]

提示：

原始树中的节点数介于?1?和?1000?之间。
每个节点的值介于?1?和?10 ^ 9?之间。

Runtime:?52 ms

Memory Usage:?20.5 MB

 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     var len:Int = 0
16     var s:[Character] = [Character]()
17     var pos:Int = 0
18     func recoverFromPreorder(_ S: String) -> TreeNode? {
19         len = S.count
20         s = Array(S)
21         return go(0)
22     }
23     
24     func go(_ dep:Int) -> TreeNode?
25     {
26         var v:Int = 0
27         while(pos < len && s[pos] >= "0" && s[pos] <= "9")
28         {
29             v = v * 10 + (s[pos].ascii - 48)
30             pos += 1
31         }
32         var cur:TreeNode? = TreeNode(v)
33         if hasEdge(dep + 1)
34         {
35             pos += (dep + 1)
36             cur?.left = go(dep + 1)
37         }
38         if hasEdge(dep + 1)
39         {
40             pos += (dep + 1)
41             cur?.right = go(dep + 1)
42         }
43         return cur
44     }
45     
46     func hasEdge(_ d:Int) -> Bool
47     {
48         if pos+d > len-1
49         {
50             return false            
51         }
52         for i in pos..<(pos + d)
53         {
54             if s[i] != "-"
55             {
56                 return false
57             }
58         }
59         return s[pos+d] != "-"
60     }
61 }
62 
63 //Character扩展 
64 extension Character  
65 {  
66   //Character转ASCII整数值(定义小写为整数值)
67    var ascii: Int {
68        get {
69            return Int(self.unicodeScalars.first?.value ?? 0)
70        }       
71     }
72 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!