{"id":4611,"date":"2019-01-05T20:53:57","date_gmt":"2019-01-06T04:53:57","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4611"},"modified":"2019-01-05T21:06:10","modified_gmt":"2019-01-06T05:06:10","slug":"leetcode-971-flip-binary-tree-to-match-preorder-traversal","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-971-flip-binary-tree-to-match-preorder-traversal\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 971. Flip Binary Tree To Match Preorder Traversal"},"content":{"rendered":"\n

Given a binary tree with N<\/code> nodes, each node has a different value from {1, ..., N}<\/code>.<\/p>\n\n\n\n

A node in this binary tree can be flipped<\/em> by swapping the left child and the right child of that node.<\/p>\n\n\n\n

Consider the sequence of N<\/code> values reported by a preorder traversal starting from the root.  Call such a sequence of N<\/code> values the voyage<\/em> of the tree.<\/p>\n\n\n\n

(Recall that a preorder traversal<\/em> of a node means we report the current node’s value, then preorder-traverse the left child, then preorder-traverse the right child.)<\/p>\n\n\n\n

Our goal is to flip the least number<\/strong> of nodes in the tree so that the voyage of the tree matches the voyage<\/code>we are given.<\/p>\n\n\n\n

If we can do so, then return a list of the values of all nodes flipped.  You may return the answer in any order.<\/p>\n\n\n\n

If we cannot do so, then return the list [-1]<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input: <\/strong>root = [1,2], voyage = [2,1]\nOutput: <\/strong>[-1]\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input: <\/strong>root = [1,2,3], voyage = [1,3,2]\nOutput: <\/strong>[1]\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input: <\/strong>root = [1,2,3], voyage = [1,2,3]\nOutput: <\/strong>[]\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= N <= 100<\/code><\/li><\/ol>\n\n\n\n
    Solution: Pre-order traversal<\/h2>\n\n\n\n
    if root->val != v[pos] return [-1]
    if root->left?->val != v[pos + 1], swap the nodes<\/p>\n\n\n\n
    \n
    c++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  vector flipMatchVoyage(TreeNode* root, vector& voyage) {\n    vector flips;\n    int pos = 0;\n    solve(root, voyage, pos, flips);\n    return flips;\n  }\nprivate:\n  void solve(TreeNode* root, const vector& voyage, int& pos, vector& flips) {\n    if (!root) return;\n    if (root->val != voyage.at(pos)) {\n      flips.clear();\n      flips.push_back(-1);\n      return;\n    }\n    if (root->left && root->left->val != voyage.at(pos + 1)) {\n      swap(root->left, root->right);\n      flips.push_back(root->val);\n    }\n    ++pos;\n    solve(root->left, voyage, pos, flips);\n    solve(root->right, voyage, pos, flips);   \n  }\n};\n<\/pre>\n\n<\/div>
    Python3<\/h2>\n
    \n\n
    \n# Author: Huahua, 60 ms\nclass Solution:\n  def flipMatchVoyage(self, root, voyage):\n    self.pos = 0\n    self.flips = []\n    def solve(root):\n      if not root: return      \n      if root.val != voyage[self.pos]:\n        self.flips = [-1]\n        return\n      if root.left and root.left.val != voyage[self.pos + 1]:\n        root.left, root.right = root.right, root.left\n        self.flips.append(root.val)\n      self.pos += 1\n      solve(root.left)\n      solve(root.right)    \n    solve(root)\n    return self.flips\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given a binary tree with N nodes, each node has a different value from {1, …, N}. A node in this binary tree can be flipped by swapping the left…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[177,290,32,28],"class_list":["post-4611","post","type-post","status-publish","format-standard","hentry","category-tree","tag-medium","tag-swap","tag-traversal","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4611","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4611"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4611\/revisions"}],"predecessor-version":[{"id":4614,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4611\/revisions\/4614"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4611"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4611"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4611"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}