[Swift Weekly Contest 118]LeetCode971.翻转二叉树以匹配先序遍
|
Given a binary tree with? A node in this binary tree can be?flipped?by swapping the left child and the right child of that node. Consider the sequence of? (Recall that a?preorder traversal?of a node means we report the current node‘s value,then preorder-traverse the left child,then preorder-traverse the right child.) Our goal is to flip the?least number?of nodes in the tree so that the voyage of the tree matches the? If we can do so,then return a?list?of the values of all nodes flipped.? You may return the answer in any order. If we cannot do so,then return the list? Example 1:
Input: root = [1,2],voyage = [2,1] Output: [-1]
Example 2:
Input: root = [1,2,3],voyage = [1,3,2] Output: [1]
Example 3:
Input: root = [1,voyage = [1,3] Output: []?
Note:
给定一个有? 通过交换节点的左子节点和右子节点，可以翻转该二叉树中的节点。 考虑从根节点开始的先序遍历报告的? （回想一下，节点的先序遍历意味着我们报告当前节点的值，然后先序遍历左子节点，再先序遍历右子节点。） 我们的目标是翻转最少的树中节点，以便树的行程与给定的行程? 如果可以，则返回翻转的所有节点的值的列表。你可以按任何顺序返回答案。 如果不能，则返回列表? 示例 1：
输入：root = [1,voyage = [2,1] 输出：[-1] 示例 2：
输入：root = [1,voyage = [1,2] 输出：[1] 示例 3：
输入：root = [1,3] 输出：[]? 提示：
20ms? 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 p:Int = 0 16 var fed:[Int] = [Int]() 17 func flipMatchVoyage(_ root: TreeNode?,_ voyage: [Int]) -> [Int] { 18 p = 0 19 if dfs(root,voyage) 20 { 21 return fed 22 } 23 else 24 { 25 fed = [Int]() 26 fed.append(-1); 27 return fed; 28 } 29 } 30 31 func dfs(_ cur: TreeNode?,_ voyage: [Int]) -> Bool 32 { 33 if cur == nil {return true} 34 if voyage[p] != cur!.val {return false} 35 p += 1 36 if cur!.left == nil 37 { 38 return dfs(cur?.right,voyage) 39 } 40 if cur!.right == nil 41 { 42 return dfs(cur?.left,voyage) 43 } 44 45 if voyage[p] == cur!.left!.val 46 { 47 var res:Bool = dfs(cur?.left,voyage) 48 if !res 49 { 50 return false 51 } 52 return dfs(cur?.right,voyage) 53 } 54 else 55 { 56 fed.append(cur!.val) 57 var res:Bool = dfs(cur?.right,voyage) 58 if !res 59 { 60 return false 61 } 62 return dfs(cur?.left,voyage) 63 } 64 } 65 } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
