本文共 1117 字，大约阅读时间需要 3 分钟。

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

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

struct Node {

int val;

Node *left;

Node *right;

Node *next;

}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

二叉树遍历一般是分为前序/中序/后序，框架如下：

traverse(Node root){       //前序遍历    traverse(root.left);    //中序遍历    traverse(root.right);    //后序遍历}

方式一：此题目可以用二叉树的前序遍历

此代码会发现示例中，没有相同父节点，5,6他们两个不能处理，所以需要改造一下代码

class Solution {       public Node connect(Node root) {           if (root == null || root.left == null) return null;        root.left.next = root.right;        connect(root.left);        connect(root.left);        return root;    }}

改造如下：

class Solution {       public Node connect(Node root) {           if (root == null) return null;        contentTwo(root.left, root.right);        return root;    }    public void contentTwo(Node node1, Node node2){           if(node1 == null || node2 == null) return;        //前序遍历        node1.next = node2;        contentTwo(node1.left, node1.right);        contentTwo(node2.left, node2.right);        //连接类似示例5,6节点的情况        contentTwo(node1.right, node2.left);    }}