题目描述

算法1

C++ 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {

        if(root==NULL) return root;
        connectTwoNode(root->left,root->right);

        return root;
    }

    void connectTwoNode(Node *node1, Node *node2){
        if(node1==NULL || node2 == NULL) return;
        node1->next = node2;
        // 连接相同父节点的两个子节点
        connectTwoNode(node1->left,node1->right);
        connectTwoNode(node2->left,node2->right);
        // 连接跨越父节点的两个子节点(看图5是2的右孩子，6是3的左孩子)
        connectTwoNode(node1->right,node2->left);

    }
};