{"id":2106,"date":"2016-08-20T20:38:24","date_gmt":"2016-08-20T12:38:24","guid":{"rendered":"http:\/\/boweihe.me\/?p=2106"},"modified":"2016-08-20T20:38:24","modified_gmt":"2016-08-20T12:38:24","slug":"leetcode-116-populating-next-right-pointers-in-each-node","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2106","title":{"rendered":"LeetCode 116. Populating Next Right Pointers in Each Node"},"content":{"rendered":"

\u601d\u8def<\/h3>\n

\u53d1\u73b0\u662f\u4e00\u4e2a\u6811\u7684\u904d\u5386\u7684\u9898\u76ee\uff0c\u800c\u4e14\u9898\u76ee\u9650\u5236\u7684\u6bd4\u8f83\u6b7b\uff0c\u662f\u4e2a\u6ee1\u4e8c\u53c9\u6811\uff0c\u8fd9\u6837\u5904\u7406\u7684\u65f6\u5019\u5c31\u907f\u514d\u4e86\u6bd4\u8f83\u70e6\u4eba\u7684\u8de8\u6811\u6307\u9488\u7684\u60c5\u51b5\u3002\u6bd4\u5982\u4e0b\u9762\u8fd9\u79cd\u5efa\u7acb4->5\u7684\u6307\u9488\uff1a<\/p>\n

    1\n  2   3\n4    5  6<\/pre>\n
\u7b2c\u4e00\u65f6\u95f4\u60f3\u5230\u7684\u89e3\u6cd5\u662f\u5f04\u4e2a\u5de5\u4f5c\u961f\u5217\uff0c\u7136\u540e\u4e00\u5c42\u4e00\u5c42\u904d\u5386\u4e0b\u53bb\u5c31\u884c\u4e86\uff0c\u8fd9\u4e2a\u89e3\u6cd5\u7684\u7a7a\u95f4\u590d\u6742\u5ea6\u662fO(n)\uff0c\u4e0d\u7b26\u5408\u9898\u76ee\u8981\u6c42\u3002\u540e\u6765\u518d\u4e00\u60f3\uff0c\u5176\u5b9e\u65e2\u7136\u4e0a\u4e00\u5c42\u5df2\u7ecf\u628a\u4e0b\u4e00\u5c42\u7684next\u6307\u9488\u5efa\u7acb\u597d\u4e86\uff0c\u5c31\u4e0d\u7528\u518d\u4ece\u5de5\u4f5c\u961f\u5217\u91cc\u53bb\u201c\u56de\u5fc6\u201d\u4e86\uff0c\u53ea\u8981\u5728\u6bcf\u4e00\u884c\u7684\u5f00\u5934\u8bb0\u4f4f\u4e0b\u4e00\u884c\u5728\u54ea\u91cc\u5c31\u884c\uff0c\u8fd9\u6837\u53ea\u8981O(1)\u7a7a\u95f4\u590d\u6742\u5ea6\u3002
\n\u53e6\u5916\u662f\u5982\u4f55\u8bbe\u7f6enext\u6307\u9488\uff0c\u4e00\u5171\u6709\u4e24\u4e2a\u60c5\u51b5\uff1a<\/p>\n
    \n
  1. node\u81ea\u5df1\u7684\u5de6\u5b69\u5b50\u548c\u53f3\u5b69\u5b50\u8fde\u8d77\u6765<\/li>\n
  2. node\u7684\u53f3\u5b69\u5b50\u4e0enode\u53f3\u4fa7\u8282\u70b9\u5b83\u7684\u5de6\u5b69\u5b50\u8fde\u8d77\u6765<\/li>\n<\/ol>\n
    \u4ee3\u7801<\/h3>\n
    O(n)\u7a7a\u95f4\u590d\u6742\u5ea6\u65b9\u6cd5<\/p>\n
    \/**\n * Definition for binary tree with next pointer.\n * struct TreeLinkNode {\n *  int val;\n *  TreeLinkNode *left, *right, *next;\n *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}\n * };\n *\/\nclass Solution {\npublic:\n    void connect(TreeLinkNode *root) {\n        queue<TreeLinkNode*> workingQ;\n        if(root == NULL)\n            return;\n        workingQ.push(root);\n        while(!workingQ.empty())\n        {\n            TreeLinkNode* node = workingQ.front();\n            workingQ.pop();\n            if(node->left == NULL || node->right == NULL)\n                continue;   \/\/Leaf node\n            node->left->next = node->right; \/\/Inner connection\n            if(node->next != NULL)\n                node->right->next = node->next->left; \/\/Outter connection\n            workingQ.push(node->left);\n            workingQ.push(node->right);\n        }\n    }\n};<\/pre>\n
    O(1)\u7a7a\u95f4\u590d\u6742\u5ea6\u65b9\u6cd5<\/p>\n
    class Solution {\npublic:\n    void connect(TreeLinkNode *root) {\n        TreeLinkNode* nextRowPtr = root;\n        TreeLinkNode* node = root;\n        bool atRowStart = true;\n        while(nextRowPtr != NULL)\n        {\n            if(node->left == NULL || node->right == NULL)\n                break;   \/\/Leaf node\n            if(atRowStart)\n            {\n                atRowStart = false;\n                nextRowPtr = node->left;\n            }\n            node->left->next = node->right; \/\/Inner connection\n            if(node->next != NULL)\n            {\n                node->right->next = node->next->left; \/\/Outter connection\n                node = node->next;\n            }\n            else\n            {\n                node = nextRowPtr;\n                atRowStart = true;  \/\/End of current row\n            }\n        }\n    }\n};<\/pre>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    \u601d\u8def \u53d1\u73b0\u662f\u4e00\u4e2a\u6811\u7684\u904d\u5386\u7684\u9898\u76ee\uff0c\u800c\u4e14\u9898\u76ee\u9650\u5236\u7684\u6bd4\u8f83\u6b7b\uff0c\u662f\u4e2a\u6ee1\u4e8c\u53c9\u6811\uff0c\u8fd9\u6837\u5904\u7406\u7684\u65f6\u5019\u5c31\u907f\u514d\u4e86\u6bd4\u8f83\u70e6\u4eba\u7684\u8de8\u6811\u6307\u9488\u7684\u60c5\u51b5\u3002\u6bd4\u5982\u4e0b\u9762\u8fd9\u79cd\u5efa\u7acb4->5\u7684\u6307\u9488\uff1a 1 2 3 4 5 6 \u7b2c\u4e00\u65f6\u95f4\u60f3\u5230\u7684\u89e3\u6cd5\u662f\u5f04\u4e2a\u5de5\u4f5c\u961f\u5217\uff0c\u7136\u540e\u4e00\u5c42\u4e00\u5c42\u904d\u5386\u4e0b\u53bb\u5c31\u884c\u4e86\uff0c\u8fd9\u4e2a\u89e3\u6cd5\u7684\u7a7a\u95f4\u590d\u6742\u5ea6\u662fO(n)\uff0c\u4e0d\u7b26\u5408\u9898\u76ee\u8981\u6c42\u3002\u540e\u6765\u518d\u4e00\u60f3\uff0c\u5176\u5b9e\u65e2\u7136\u4e0a\u4e00\u5c42\u5df2\u7ecf\u628a\u4e0b\u4e00\u5c42\u7684next\u6307\u9488\u5efa\u7acb\u597d\u4e86\uff0c\u5c31\u4e0d\u7528\u518d\u4ece\u5de5\u4f5c\u961f\u5217\u91cc\u53bb\u201c\u56de\u5fc6\u201d\u4e86\uff0c\u53ea\u8981\u5728\u6bcf\u4e00\u884c\u7684\u5f00\u5934\u8bb0\u4f4f\u4e0b\u4e00\u884c\u5728\u54ea\u91cc\u5c31\u884c\uff0c\u8fd9\u6837\u53ea\u8981O(1)\u7a7a\u95f4\u590d\u6742\u5ea6\u3002 \u53e6\u5916\u662f\u5982\u4f55\u8bbe\u7f6enext\u6307\u9488\uff0c\u4e00\u5171\u6709\u4e24\u4e2a\u60c5\u51b5\uff1a node\u81ea\u5df1\u7684\u5de6\u5b69\u5b50\u548c\u53f3\u5b69\u5b50\u8fde\u8d77\u6765 node\u7684\u53f3\u5b69\u5b50\u4e0enode\u53f3\u4fa7\u8282\u70b9\u5b83\u7684\u5de6\u5b69\u5b50\u8fde\u8d77\u6765 \u4ee3\u7801 O(n)\u7a7a\u95f4\u590d\u6742\u5ea6\u65b9\u6cd5 \/** * Definition for binary tree with next pointer. * struct TreeLinkNode { * int val; * TreeLinkNode *left, *right, *next; * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} * }; *\/ class Solution { public: void connect(TreeLinkNode *root) { […]<\/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":[66,133,164],"class_list":["post-2106","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj","tag-133","tag-164"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2106","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=2106"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2106\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2106"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2106"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2106"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}