填充每个节点的下一个左侧节点指针

题目描述

  给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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

  填充它的每个next指针，让这个指针指向其下一个左侧节点。如果找不到下一个右侧节点，则将next指针设置为NULL。初始状态下，所有next指针都被设置为NULL

输入输出样例

  给定一个二叉树如图A所示，函数应该填充它的每个next指针,以指向其下一个右侧节点，如图B所示。序列化输出按层序遍历排列，同一层节点由next指针连接，’#’标志着每一层的结束。

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]

题解

  首先这题主要问题在于使用指向右子树节点的next。简单的只存在左右子树,即这是一个具有两层的树。我们可以直接使用递归来进行处理，大致代码如下

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr || root->left == nullptr) 
            return root;
        root->left->next = root->right;

        connect(root->left);
        connect(root->right);

        return root;
    }
};

  但是对于多层的树来说，这样的解法就存在一定的缺陷。对于超过两层的树，会分叉多个子节点。继续使用上面的解法就会导致左子树处理完成，而右子树却没有处理的状况。
  我们可以使用函数来处理对于多个节点的问题，代码如下：

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) return root;
        connectTwoTree(root->left,root->right);
        return root;
    }
    void connectTwoTree(Node* node,Node* node1) {
        if (node == nullptr || node1 == nullptr) return;

        node->next = node1;

        connectTwoTree(node->left,node->right);
        connectTwoTree(node1->left,node1->right);

        connectTwoTree(node->right,node1->left);
    }
};