{"id":7460,"date":"2020-10-04T11:42:42","date_gmt":"2020-10-04T18:42:42","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7460"},"modified":"2020-10-04T13:32:53","modified_gmt":"2020-10-04T20:32:53","slug":"leetcode-1609-even-odd-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-1609-even-odd-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1609. Even Odd Tree"},"content":{"rendered":"\n<p>A binary tree is named&nbsp;<strong>Even-Odd<\/strong>&nbsp;if it meets the following conditions:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The root of the binary tree is at level index&nbsp;<code>0<\/code>, its children are at level index&nbsp;<code>1<\/code>, their children are at level index&nbsp;<code>2<\/code>, etc.<\/li><li>For every&nbsp;<strong>even-indexed<\/strong>&nbsp;level, all nodes at the level have&nbsp;<strong>odd<\/strong>&nbsp;integer values in&nbsp;<strong>strictly increasing<\/strong>&nbsp;order (from left to right).<\/li><li>For every&nbsp;<strong>odd-indexed<\/strong>&nbsp;level, all nodes at the level have&nbsp;<strong>even<\/strong>&nbsp;integer values in&nbsp;<strong>strictly decreasing<\/strong>&nbsp;order (from left to right).<\/li><\/ul>\n\n\n\n<p>Given the&nbsp;<code>root<\/code>&nbsp;of a binary tree,&nbsp;<em>return&nbsp;<\/em><code>true<\/code><em>&nbsp;if the binary tree is&nbsp;<strong>Even-Odd<\/strong>, otherwise return&nbsp;<\/em><code>false<\/code><em>.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/09\/15\/sample_1_1966.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,10,4,3,null,7,9,12,8,6,null,null,2]\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> The node values on each level are:\nLevel 0: [1]\nLevel 1: [10,4]\nLevel 2: [3,7,9]\nLevel 3: [12,8,6,2]\nSince levels 0 and 2 are all odd and increasing, and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/09\/15\/sample_2_1966.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [5,4,2,3,3,7]\n<strong>Output:<\/strong> false\n<strong>Explanation:<\/strong> The node values on each level are:\nLevel 0: [5]\nLevel 1: [4,2]\nLevel 2: [3,3,7]\nNode values in the level 2 must be in strictly increasing order, so the tree is not Even-Odd.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/09\/22\/sample_1_333_1966.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [5,9,1,3,5,7]\n<strong>Output:<\/strong> false\n<strong>Explanation:<\/strong> Node values in the level 1 should be even integers.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1]\n<strong>Output:<\/strong> true\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]\n<strong>Output:<\/strong> true\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The number of nodes in the tree is in the range&nbsp;<code>[1, 10<sup>5<\/sup>]<\/code>.<\/li><li><code>1 &lt;= Node.val &lt;= 10<sup>6<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: DFS<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  bool isEvenOddTree(TreeNode* root) {\n    vector<int> vals;\n    function<bool(TreeNode*, int)> dfs = [&](TreeNode* root, int d) {\n      if (!root) return true;\n      if (vals.size() <= d)\n        vals.push_back(d % 2 == 0 ? -1 : INT_MAX);\n      int&#038; val = vals[d];\n      if (d % 2 == 0)\n        if (root->val % 2 == 0 || root->val <= val) return false;\n      if (d % 2 == 1)\n        if (root->val % 2 == 1 || root->val >= val) return false;\n      val = root->val;\n      return dfs(root->left, d + 1) && dfs(root->right, d + 1);\n    };\n    return dfs(root, 0);\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass Solution:\n  def isEvenOddTree(self, root: TreeNode) -> bool:\n    vals = {}\n    def dfs(root: TreeNode, d: int) -> bool:\n      if not root: return True\n      if d not in vals: vals[d] = 0 if d % 2 == 0 else 10**7\n      comp = int.__ge__ if d % 2 else int.__le__      \n      if root.val % 2 == d % 2 or comp(root.val, vals[d]): return False      \n      vals[d] = root.val\n      return dfs(root.left, d + 1) and dfs(root.right, d + 1)\n    return dfs(root, 0)\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: BFS<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(n)<\/p>\n\n\n\n<p><\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\"># Author: Huahua\nclass Solution:\n  def isEvenOddTree(self, root: TreeNode) -&gt; bool:\n    q = collections.deque([root])\n    odd = 1\n    while q:\n      prev = 0 if odd else 10**7\n      for _ in range(len(q)):\n        root = q.popleft()\n        if not root: continue\n        comp = int.__le__ if odd else int.__ge__        \n        if root.val % 2 != odd or comp(root.val, prev): return False        \n        prev = root.val\n        q += (root.left, root.right)        \n      odd = 1 - odd\n    return True\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A binary tree is named&nbsp;Even-Odd&nbsp;if it meets the following conditions: The root of the binary tree is at level index&nbsp;0, its children are at level&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-7460","post","type-post","status-publish","format-standard","hentry","category-uncategorized","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7460","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=7460"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7460\/revisions"}],"predecessor-version":[{"id":7470,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7460\/revisions\/7470"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7460"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7460"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7460"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}