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

题目

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

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

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

初始状态下，所有 next 指针都被设置为 NULL。
示例：
解释： 给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

解题思路

左结点的next指向右结点，然后递归调用他们的叶子结点即可。

代码如下

public Node connect(Node root) {
        if(root == null) return null;
        root.next = null;
        connect(root.left, root.right);
        return root;
    }
    public void connect(Node left, Node right) {
        if(left == null) return;
        left.next = right;
        connect(left.left, left.right);
        connect(left.right, right.left);
        connect(right.left, right.right);
        right.next = null;
    }

提交结果

成功
显示详情
执行用时 : 1 ms, 在Populating Next Right Pointers in Each Node的Java提交中击败了86.12% 的用户
内存消耗 : 34.8 MB, 在Populating Next Right Pointers in Each Node的Java提交中击败了89.07% 的用户