{"id":582,"date":"2013-09-08T19:16:11","date_gmt":"2013-09-08T11:16:11","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=582"},"modified":"2013-09-08T19:16:11","modified_gmt":"2013-09-08T11:16:11","slug":"1043-is-it-a-binary-search-tree-25","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=582","title":{"rendered":"1043. Is It a Binary Search Tree (25)"},"content":{"rendered":"<p>\u65f6\u95f4\u9650\u5236\uff1a400ms<br \/>\nA Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:<\/p>\n<ul>\n<li>The left subtree of a node contains only nodes with keys less than the node&#8217;s key.<\/li>\n<li>The right subtree of a node contains only nodes with keys greater than or equal to the node&#8217;s key.<\/li>\n<li>Both the left and right subtrees must also be binary search trees.<\/li>\n<\/ul>\n<p>If we swap the left and right subtrees of every node, then the resulting tree is called the Mirror Image of a BST.<br \/>\nNow given a sequence of integer keys, you are supposed to tell if it is the preorder traversal sequence of a BST or the mirror image of a BST.<br \/>\n<b>Input Specification:<\/b><br \/>\nEach input file contains one test case. For each case, the first line contains a positive integer N (&lt;=1000). Then N integer keys are given in the next line. All the numbers in a line are separated by a space.<br \/>\n<b>Output Specification:<\/b><br \/>\nFor each test case, first print in a line &#8220;YES&#8221; if the sequence is the preorder traversal sequence of a BST or the mirror image of a BST, or &#8220;NO&#8221; if not. Then if the answer is &#8220;YES&#8221;, print in the next line the postorder traversal sequence of that tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.<br \/>\n<b>Sample Input 1:<\/b><\/p>\n<pre>7\n8 6 5 7 10 8 11<\/pre>\n<p><b>Sample Output 1:<\/b><\/p>\n<pre>YES\n5 7 6 8 11 10 8<\/pre>\n<p><b>Sample Input 2:<\/b><\/p>\n<pre>7\n8 10 11 8 6 7 5<\/pre>\n<p><b>Sample Output 2:<\/b><\/p>\n<pre>YES\n11 8 10 7 5 6 8<\/pre>\n<p><b>Sample Input 3:<\/b><\/p>\n<pre>7\n8 6 8 5 10 9 11<\/pre>\n<p><b>Sample Output 3:<\/b><\/p>\n<pre>NO<\/pre>\n<p>===================================<br \/>\n\u4e8c\u53c9\u641c\u7d22\u6811\u4e0e\u201c\u955c\u50cf\u201d\u7684\u4e8c\u53c9\u641c\u7d22\u6811\uff0c\u5176\u5b9e\u5bf9\u79f0\u7684\u4e1c\u897f\u53ea\u662f\u90e8\u5206\u7279\u6b8a\u5316\u4e86\u4e00\u4e0b\uff0c\u6240\u4ee5\u641e\u5b9a\u975e\u5bf9\u79f0\u7684\u5c31\u884c\u3002<br \/>\n\u60f3\u4e86\u534a\u5929\u600e\u4e48\u7528\u5806\u6808\u4ec0\u4e48\u7684\u5b9e\u73b0\uff0c\u5176\u5b9e\u628a\u81ea\u5df1\u7ed5\u7d27\u4e86\u65e0\u5e95\u6d1e\uff0c\u5e72\u8106\u81ea\u5b9a\u4e49\u7ed3\u6784\u5f04\u561b\uff01<br \/>\n\u57fa\u672c\u601d\u8def\u5982\u4e0b\uff08\u5bf9BST\u6765\u8bf4\u7684\uff09<br \/>\n<code lang=\"python\"><br \/>\n\u5de5\u4f5c\u961f\u5217q = \u8f93\u5165\u503c<br \/>\n\u7ed3\u679c\u961f\u5217result = []<br \/>\n\u521d\u59cb\u5316\u6839\u8282\u70b9root(value)<br \/>\nroot.left_bound = [-INF, value]<br \/>\nroot.right_bound = [value, INF]<br \/>\ncurrNode = root<br \/>\nwhile len(q)>0 and currNode!=None:<br \/>\n    \u5f53\u524d\u961f\u9996\u6570\u503c\u4e3an<br \/>\n    if n\u80fd\u653e\u5728\u5f53\u524d\u8282\u70b9\u5de6\u4fa7:<br \/>\n        \u65b0\u5efa\u8282\u70b9newNode<br \/>\n        newNode.left_bound = [ currNode.left_bound[0], n]<br \/>\n        newNode.right_bound = [ n, currNode.left_bound[1]]<br \/>\n        newNode.parent = currNode<br \/>\n        q.pop()<br \/>\n    elif \u80fd\u653e\u5728\u53f3\u4fa7:<br \/>\n        \u65b0\u5efa\u8282\u70b9newNode<br \/>\n        newNode.left_bound = [ currNode.right_bound[0], n]<br \/>\n        newNode.right_bound = [ n, currNode.right_bound[1]]<br \/>\n        newNode.parent = currNode<br \/>\n        ######<br \/>\n        currNode.cannotPlaceLeft = true<br \/>\n        ######<br \/>\n        q.pop()<br \/>\n    else:<br \/>\n        result.push(currNode.value)<br \/>\n        ######<br \/>\n        currNode.cannotPlaceLeft = true<br \/>\n        ######<br \/>\n        currNode = currNode.parent<br \/>\n\u4e00\u5207\u5904\u7406\u5b8c\u4e4b\u540e\uff0c<br \/>\nwhile currNode != None:<br \/>\n    result.push(currNode.value)<br \/>\n    currNode = currNoew.parent<br \/>\n<\/code><br \/>\n\u91cc\u9762#####\u4e2d\u95f4\u7684\u4e00\u4e2a\u5e03\u5c14\u53d8\u91cf\u662f\u9632\u6b62\u91cd\u590d\u8bbf\u95ee\u5de6\u4fa7\u503c\u8bbe\u5b9a\u7684\uff0c\u6bd4\u5982\u8bf4\u5982\u4e0b\u60c5\u51b5<br \/>\n  8<br \/>\nX   10<br \/>\n\u6b64\u65f6\u5de6\u8fb9\u6ca1\u6709\u4e1c\u897f\uff0c\u4f46\u662f\u5df2\u7ecf\u8bbf\u95ee\u8fc7\u4e86\uff0c\u5982\u679c\u4e0d\u8bbe\u7f6e\u4e00\u4e2a\u5e03\u5c14\u503c\u5224\u65ad\u7684\u8bdd\uff0c\u5047\u8bbe\u5f53\u524d\u6709\u90a3\u4e48\u4e00\u4e2a\u503c=6\u7684\u5143\u7d20<br \/>\n\u5f53\u524d\u5904\u7406\u4f4d\u7f6e\u572810\uff0c\u53d1\u73b06\u653e\u4e0d\u8fdb\u53bb\uff0c\u7136\u540e\u79fb\u52308\u7684\u4f4d\u7f6e<br \/>\n\u5c31\u4f1a\u89c9\u5f978\u5de6\u8fb9\u53ef\u4ee5\u585e\u8fdb\u53bb<br \/>\n\u4f46\u5176\u5b9e\u5df2\u7ecf\u662f\u975e\u6cd5\u64cd\u4f5c\u4e86<br \/>\n=================================================================<br \/>\n<code lang=\"c++\"><br \/>\n#include <stdio.h><br \/>\n#include <queue><br \/>\nusing namespace std;<br \/>\nconst int INFI = 65535;<br \/>\nstruct Node<br \/>\n{<br \/>\n\tint value;<br \/>\n\tNode* left;<br \/>\n\tNode* right;<br \/>\n\tNode* parent;<br \/>\n\tint left_bound[2];<br \/>\n\tint right_bound[2];<br \/>\n\tbool left_tried; \/\/\u5df2\u7ecf\u5c1d\u8bd5\u8fc7\u5de6\u4fa7<br \/>\n\tvoid setLeftBound(int val0, int val1)<br \/>\n\t{<br \/>\n\t\tleft_bound[0] = val0;<br \/>\n\t\tleft_bound[1] = val1;<br \/>\n\t}<br \/>\n\tvoid setRightBound(int val0, int val1)<br \/>\n\t{<br \/>\n\t\tright_bound[0] = val0;<br \/>\n\t\tright_bound[1] = val1;<br \/>\n\t}<br \/>\n\tbool canPlaceLeft(int val)<br \/>\n\t{<br \/>\n\t\tif(left != NULL)<br \/>\n\t\t\treturn false;<br \/>\n\t\tif(left_tried)<br \/>\n\t\t\treturn false;<br \/>\n\t\tif(val >= left_bound[0] && val < left_bound[1])\n\t\t\treturn true;\n\t\treturn false;\n\t}\n\tbool canPlaceRight(int val)\n\t{\n\t\tif(right != NULL)\n\t\t\treturn false;\n\t\tif(val >= right_bound[0] && val < right_bound[1])\n\t\t\treturn true;\n\t\treturn false;\n\t}\n\tNode()\n\t{\n\t\tleft = NULL;\n\t\tright = NULL;\n\t\tparent = NULL;\n\t\tsetLeftBound(-INFI, INFI);\n\t\tsetRightBound(-INFI, INFI);\n\t\tleft_tried = false;\n\t}\n};\nqueue<int> tryBST(queue<int> input)<br \/>\n{<br \/>\n\tqueue<int> result;<br \/>\n\tNode root;<br \/>\n\troot.value = input.front();<br \/>\n\troot.setLeftBound(-INFI, root.value);<br \/>\n\troot.setRightBound(root.value, INFI);<br \/>\n\tinput.pop();<br \/>\n\tNode* currNode = &root;<br \/>\n\twhile(!input.empty() && currNode!=NULL)<br \/>\n\t{<br \/>\n\t\tint currVal = input.front();<br \/>\n\t\tif(currNode->canPlaceLeft(currVal))<br \/>\n\t\t{<br \/>\n\t\t\t\/\/\u53ef\u4ee5\u653e\u5728\u5de6\u4fa7<br \/>\n\t\t\tNode *pNewNode = new Node;<br \/>\n\t\t\tpNewNode->setLeftBound(currNode->left_bound[0], currVal);<br \/>\n\t\t\tpNewNode->setRightBound(currVal, currNode->left_bound[1]);<br \/>\n\t\t\tpNewNode->parent = currNode;<br \/>\n\t\t\tpNewNode->value = currVal;<br \/>\n\t\t\tcurrNode->left = pNewNode;<br \/>\n\t\t\tcurrNode = pNewNode;<br \/>\n\t\t\tinput.pop();<br \/>\n\t\t}<br \/>\n\t\telse if(currNode->canPlaceRight(currVal))<br \/>\n\t\t{<br \/>\n\t\t\t\/\/\u53ef\u4ee5\u653e\u5728\u53f3\u4fa7<br \/>\n\t\t\tNode *pNewNode = new Node;<br \/>\n\t\t\tpNewNode->setLeftBound(currNode->right_bound[0], currVal);<br \/>\n\t\t\tpNewNode->setRightBound(currVal, currNode->right_bound[1]);<br \/>\n\t\t\tpNewNode->parent = currNode;<br \/>\n\t\t\tpNewNode->value = currVal;<br \/>\n\t\t\tcurrNode->right = pNewNode;<br \/>\n\t\t\tcurrNode->left_tried = true;<br \/>\n\t\t\tcurrNode = pNewNode;<br \/>\n\t\t\tinput.pop();<br \/>\n\t\t}<br \/>\n\t\telse<br \/>\n\t\t{<br \/>\n\t\t\tresult.push(currNode->value);<br \/>\n\t\t\tcurrNode->left_tried = true;<br \/>\n\t\t\tcurrNode = currNode->parent;<br \/>\n\t\t}<br \/>\n\t}<br \/>\n\twhile(currNode != NULL)<br \/>\n\t{<br \/>\n\t\t\/\/\u4e00\u76f4\u9012\u5f52\u5230\u6839\u90e8\u52a0\u5165\u904d\u5386\u7ed3\u679c<br \/>\n\t\tresult.push(currNode->value);<br \/>\n\t\tcurrNode = currNode->parent;<br \/>\n\t}<br \/>\n\treturn result;<br \/>\n}<br \/>\nqueue<int> tryBSTRev(queue<int> input)<br \/>\n{<br \/>\n\tqueue<int> result;<br \/>\n\tNode root;<br \/>\n\troot.value = input.front();<br \/>\n\troot.setRightBound(-INFI, root.value);<br \/>\n\troot.setLeftBound(root.value, INFI);<br \/>\n\tinput.pop();<br \/>\n\tNode* currNode = &root;<br \/>\n\twhile(!input.empty() && currNode!=NULL)<br \/>\n\t{<br \/>\n\t\tint currVal = input.front();<br \/>\n\t\tif(currNode->canPlaceLeft(currVal))<br \/>\n\t\t{<br \/>\n\t\t\t\/\/\u53ef\u4ee5\u653e\u5728\u5de6\u4fa7<br \/>\n\t\t\tNode *pNewNode = new Node;<br \/>\n\t\t\tpNewNode->setRightBound(currNode->left_bound[0], currVal);<br \/>\n\t\t\tpNewNode->setLeftBound(currVal, currNode->left_bound[1]);<br \/>\n\t\t\tpNewNode->parent = currNode;<br \/>\n\t\t\tpNewNode->value = currVal;<br \/>\n\t\t\tcurrNode->left = pNewNode;<br \/>\n\t\t\tcurrNode = pNewNode;<br \/>\n\t\t\tinput.pop();<br \/>\n\t\t}<br \/>\n\t\telse if(currNode->canPlaceRight(currVal))<br \/>\n\t\t{<br \/>\n\t\t\t\/\/\u53ef\u4ee5\u653e\u5728\u53f3\u4fa7<br \/>\n\t\t\tNode *pNewNode = new Node;<br \/>\n\t\t\tpNewNode->setRightBound(currNode->right_bound[0], currVal);<br \/>\n\t\t\tpNewNode->setLeftBound(currVal, currNode->right_bound[1]);<br \/>\n\t\t\tpNewNode->parent = currNode;<br \/>\n\t\t\tpNewNode->value = currVal;<br \/>\n\t\t\tcurrNode->right = pNewNode;<br \/>\n\t\t\tcurrNode->left_tried = true;<br \/>\n\t\t\tcurrNode = pNewNode;<br \/>\n\t\t\tinput.pop();<br \/>\n\t\t}<br \/>\n\t\telse<br \/>\n\t\t{<br \/>\n\t\t\tresult.push(currNode->value);<br \/>\n\t\t\tcurrNode->left_tried = true;<br \/>\n\t\t\tcurrNode = currNode->parent;<br \/>\n\t\t}<br \/>\n\t}<br \/>\n\twhile(currNode != NULL)<br \/>\n\t{<br \/>\n\t\t\/\/\u4e00\u76f4\u9012\u5f52\u5230\u6839\u90e8\u52a0\u5165\u904d\u5386\u7ed3\u679c<br \/>\n\t\tresult.push(currNode->value);<br \/>\n\t\tcurrNode = currNode->parent;<br \/>\n\t}<br \/>\n\treturn result;<br \/>\n}<br \/>\nint main()<br \/>\n{<br \/>\n\tqueue<int> input;<br \/>\n\tint N;<br \/>\n\tscanf(\"%d\", &N);<br \/>\n\tfor(int i=0; i<n; i++)\n\t{\n\t\tint val;\n\t\tscanf(\"%d\", &#038;val);\n\t\tinput.push(val);\n\t}\n\t\/\/\n\tqueue<int> result1 = tryBST(input);<br \/>\n\tif(result1.size() == input.size())<br \/>\n\t{<br \/>\n\t\tprintf(\"YESn\");<br \/>\n\t\twhile(!result1.empty())<br \/>\n\t\t{<br \/>\n\t\t\tprintf(\"%d\", result1.front());<br \/>\n\t\t\tif(result1.size() != 1)<br \/>\n\t\t\t\tprintf(\" \");<br \/>\n\t\t\tresult1.pop();<br \/>\n\t\t}<br \/>\n\t\treturn 0;<br \/>\n\t}<br \/>\n\tresult1 = tryBSTRev(input);<br \/>\n\tif(result1.size() == input.size())<br \/>\n\t{<br \/>\n\t\tprintf(\"YESn\");<br \/>\n\t\twhile(!result1.empty())<br \/>\n\t\t{<br \/>\n\t\t\tprintf(\"%d\", result1.front());<br \/>\n\t\t\tif(result1.size() != 1)<br \/>\n\t\t\t\tprintf(\" \");<br \/>\n\t\t\tresult1.pop();<br \/>\n\t\t}<br \/>\n\t\treturn 0;<br \/>\n\t}<br \/>\n\tprintf(\"NO\");<br \/>\n\t\/\/<br \/>\n\treturn 0;<br \/>\n}<br \/>\n<\/code><\/p>\n<pre>\n\u6d4b\u8bd5\u70b9\t\u7ed3\u679c\t\u7528\u65f6(ms)\t\u5185\u5b58(kB)\t\u5f97\u5206\/\u6ee1\u5206\n0\t\u7b54\u6848\u6b63\u786e\t0\t710\t6\/6\n1\t\u7b54\u6848\u6b63\u786e\t0\t790\t6\/6\n2\t\u7b54\u6848\u6b63\u786e\t0\t710\t2\/2\n3\t\u7b54\u6848\u6b63\u786e\t0\t720\t3\/3\n4\t\u7b54\u6848\u6b63\u786e\t0\t790\t3\/3\n5\t\u7b54\u6848\u6b63\u786e\t0\t700\t2\/2\n6\t\u7b54\u6848\u6b63\u786e\t0\t790\t2\/2\n7\t\u7b54\u6848\u6b63\u786e\t0\t790\t1\/1\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u65f6\u95f4\u9650\u5236\uff1a400ms A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node&#8217;s key. The right subtree of a node contains only nodes with keys greater than or equal to the node&#8217;s key. Both the [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-582","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/582","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=582"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/582\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=582"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=582"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=582"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}