第10天了。
今天的题目是 117. Populating Next Right Pointers in Each Node II :
Given a binary tree
1struct Node {2 int val;3 Node *left;4 Node *right;5 Node *next;6}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL
.
Initially, all next pointers are set to NULL
.
Example:
1Input: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":null,"next":null,"right":{"$id":"6","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}2
3Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}4
5Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.
Note:
- You may only use constant extra space.
- Recursive approach is fine, implicit stack space does not count as extra space for this problem.
这是一道之前没做出来的问题,最开始想出来的解法也和之前差不多,大概的想法是递归求解时返回子树的最左和最右节点,然后通过一些判断来相连,但是这个问题主要是没法处理两个子树高度不一样的问题。
后面尝试用分治的方法来做,主要的想法是,假设我现在已经有了连接好的左子树和右子树,现在只需要将两个子树连接起来即可。而连接方法就是一层一层的去连接两个子树:
1Node *nextLayer(Node *root) {2 while(root) {3 if (root->left) return root->left;4 if (root->right) return root->right;5 root = root->next;6 }7 return nullptr;8}9void connectLeftRight(Node *left, Node *right) {10 // level 111 Node *pl, *pr;12 while(left && right) {13 pl = left;14 pr = right;15
17 collapsed lines
16 // next layer17 left = nextLayer(left);18 right = nextLayer(right);19
20 // connect left and right tree in this layer21 while(pl->next) pl = pl->next;22 pl->next = pr;23 }24}25
26Node* connect1(Node* root) {27 if (root == nullptr) return nullptr;28 Node *left = connect1(root->left);29 Node *right = connect1(root->right);30 connectLeftRight(left, right);31 return root;32}
这个方法的时间复杂度大概是O(h^2)
,其中h
是树的高度。
后面又发现一种方法,这种方法大概的思路是连接孩子,然后在递归求解。这样会保证在求解到root
节点时,root
节点的next
是已知的,同时在连接孩子时,需要利用到右子树的next
指针,所以需要先求解右子树再求解左子树。
1void connectChild(Node *root) {2 if (root == nullptr) return;3
4 if (root->left) {5 if (root->right) root->left->next = root->right;6 else root->left->next = helper(root->next);7 }8 if (root->right) {9 root->right->next = helper(root->next);10 }11
12}13
14Node *helper(Node *root) {15 if (root == nullptr) return nullptr;13 collapsed lines
16 else if (root->left) return root->left;17 else if (root->right) return root->right;18 else return helper(root->next);19}20
21Node* connect2(Node* root) {22 if (root ==nullptr) return nullptr;23 connectChild(root);24 // 先求右边的。25 connect2(root->right);26 connect3(root->left);27 return root;28}