117. Populating Next Right Pointers in Each Node II

Given a binary tree

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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.

Follow up:

• You may only use constant extra space.
• Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: 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. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

• The number of nodes in the given tree is less than 6000.
• -100 <= node.val <= 100

---

本题在LeetCode Populating Next Right Pointers in Each Node的基础上，扩展了二叉树的形式，并不要求二叉树一定是满二叉树（题中的完全二叉树），而是一个一般的二叉树。 这个时候就会遇到一些问题，比如下面的二叉树。

         1
       /  \
      2    3
     / \    \
    4   5    7
   /          \
  8            9

如果还按原来的先左孩子后右孩子的DFS，则第一次深度遍历完之后是这样的：

         1
       /  \
      2 -> 3
     / \    \
    4 ->5    7
   /          \
  8            9

此时要找8的next时就比较麻烦，因为在上一层到5时断了，没有5->7，所以找不到9号节点。所以需要修改为先对右孩子遍历，再对左孩子遍历，这样父亲一层的next就都完备了。 另外代码中还统一了child是左孩子和右孩子的代码，都是在父亲一层不断找next，直到找到合法next或者NULL。不过针对右孩子时，需要注意，为了不让其next指向左兄弟，增加了tmp != parent的约束。 完整代码如下：

class Solution {
public:
    void dfs(TreeLinkNode* child, TreeLinkNode* parent)
    {
        if (child == NULL)
            return;
        if (parent) {
            TreeLinkNode* tmp = parent;
            while (tmp) {
                if (tmp != parent && tmp->left && child != tmp->left) {
                    child->next = tmp->left;
                    break;
                }
                if (tmp->right && child != tmp->right) {
                    child->next = tmp->right;
                    break;
                }
                tmp = tmp->next;
            }
        }
        dfs(child->right, child);
        dfs(child->left, child);
    }
    void connect(TreeLinkNode* root) { dfs(root, NULL); }
};

本代码提交AC，用时32MS。

二刷。简单易懂但是比较啰嗦的代码：

class Solution {
public:
	void point2right(Node* par, Node* cur) {
		if (cur == NULL)return;

		if (par != NULL) {
			if (cur == par->left) {
				if (par->right != NULL) {
					cur->next = par->right;
				}
				else {
					Node* tmp = par->next;
					while (tmp != NULL) {
						if (tmp->left != NULL) {
							cur->next = tmp->left;
							break;
						}
						else if (tmp->right != NULL) {
							cur->next = tmp->right;
							break;
						}
						tmp = tmp->next;
					}
				}
			}
			else {
				// 和上面一段是一样的
				Node* tmp = par->next;
				while (tmp != NULL) {
					if (tmp->left != NULL) {
						cur->next = tmp->left;
						break;
					}
					else if (tmp->right != NULL) {
						cur->next = tmp->right;
						break;
					}
					tmp = tmp->next;
				}
			}
		}
		point2right(cur, cur->right);
		point2right(cur, cur->left);
	}
	Node* connect(Node* root) {
		if (root == NULL || (root->left == NULL && root->right == NULL))return root;
		point2right(NULL, root);
		return root;
	}
};

这一题的关键是要先递归右子树，再递归左子树。本代码提交AC，用时16MS。