{"id":6405,"date":"2020-03-08T00:53:52","date_gmt":"2020-03-08T08:53:52","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6405"},"modified":"2020-03-08T00:54:50","modified_gmt":"2020-03-08T08:54:50","slug":"leetcode-1372-longest-zigzag-path-in-a-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1372-longest-zigzag-path-in-a-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1372. Longest ZigZag Path in a Binary Tree"},"content":{"rendered":"\n<p>Given a binary tree&nbsp;<code>root<\/code>, a&nbsp;ZigZag path for a binary tree is defined as follow:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Choose&nbsp;<strong>any&nbsp;<\/strong>node in the binary tree and a direction (right or left).<\/li><li>If the current direction is right then move to the right child of the current node otherwise move to the left child.<\/li><li>Change the direction from right to left or right to left.<\/li><li>Repeat the second and third step until you can&#8217;t move in the tree.<\/li><\/ul>\n\n\n\n<p>Zigzag length is defined as the number of nodes visited &#8211; 1. (A single node has a length of 0).<\/p>\n\n\n\n<p>Return&nbsp;the longest&nbsp;<strong>ZigZag<\/strong>&nbsp;path contained in that tree.<\/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\/01\/22\/sample_1_1702.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> Longest ZigZag path in blue nodes (right -&gt; left -&gt; right).\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\/01\/22\/sample_2_1702.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1,1,1,null,1,null,null,1,1,null,1]\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> Longest ZigZag path in blue nodes (left -&gt; right -&gt; left -&gt; right).\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> root = [1]\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Each tree has at most&nbsp;<code>50000<\/code>&nbsp;nodes..<\/li><li>Each node&#8217;s value is between&nbsp;<code>[1, 100]<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Recursion<\/strong><\/h2>\n\n\n\n<p>For each node return <br>1. max ZigZag length if go left<br>2. max ZigZag length if go right<br>3. maz ZigZag length within the subtree<br><br>ZigZag(root):<br>  ll, lr, lm = ZigZag(root.left)<br>  rl, rr, rm = ZigZag(root.right)<br>return (lr+1, rl + 1, max(lr+1, rl+1, lm, rm))<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(h)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int longestZigZag(TreeNode* root) {    \n    return get<2>(ZigZag(root));\n  }\n    \n  \/\/ Returns {left, right, max}\n  tuple<int, int, int> ZigZag(TreeNode* root) {\n    if (!root) return {-1, -1, -1};\n    auto [ll, lr, lm] = ZigZag(root->left);\n    auto [rl, rr, rm] = ZigZag(root->right);\n    int l = lr + 1;\n    int r = rl + 1;\n    return {l, r, max({l, r, lm, rm})};\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"Python\">\n# Author: Huahua\nclass Solution:\n  def longestZigZag(self, root: TreeNode) -> int:\n    def ZigZag(node):\n      if not node: return (-1, -1, -1)\n      ll, lr, lm = ZigZag(node.left)\n      rl, rr, rm = ZigZag(node.right)\n      return (lr + 1, rl + 1, max(lr + 1, rl + 1, lm, rm))\n    return ZigZag(root)[2]\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a binary tree&nbsp;root, a&nbsp;ZigZag path for a binary tree is defined as follow: Choose&nbsp;any&nbsp;node in the binary tree and a direction (right or left).&#8230;<\/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":[566,177,376,17],"class_list":["post-6405","post","type-post","status-publish","format-standard","hentry","category-tree","tag-longest-path","tag-medium","tag-on","tag-recursion","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6405","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=6405"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6405\/revisions"}],"predecessor-version":[{"id":6407,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6405\/revisions\/6407"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6405"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6405"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6405"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}