LeetCode - 116. 填充每个节点的下一个右侧节点指针 - java

文章目录

LeetCode - 116. 填充每个节点的下一个右侧节点指针

题目解析

给了我们一棵两种特殊的二叉树之一：满二叉树,让我们将其转换成为孩子兄弟表示法。

解题思维一 ： 层序遍历

可参考 这篇文章学习二叉树 这一篇就够了
找到框选的目录，点击跳转，里面讲的非常详细！

唯一需要注意的是：
1、我们不是打印，而是利用层序遍历来实现我们树节点next域值的修改。
2、获取每一层的节点个数，方便判断该节点是否有兄弟节点。

代码如下

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

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/classSolution{publicNodeconnect(Node root){if(root ==null){return root;}Queue<Node> queue =newLinkedList<>();
        queue.offer(root);while(!queue.isEmpty()){int size = queue.size();// 获取该层的节点个数for(int i =0;i < size;i++){Node tmp = queue.poll();if(i < size -1){// 说明 i 节点的右侧至少2个节点
                    tmp.next = queue.peek();}// 将不为空的左右子树 入队if(tmp.left !=null){
                    queue.offer(tmp.left);}if(tmp.right !=null){
                    queue.offer(tmp.right);}}}return root;}}

解题思维二： 使用已建立的 next 指针

一个棵树中，只有两种情况下，才有next的值。
第一种情况：两个节点之间是同一个父亲节点。

第二种情况：两个节点之间，不是同一个父亲节点。

思路：定义一个 leftRoot = root ,意为永远指向 最左边的根结点。

此时，是符合第一种情况【两个节点是同一个父亲节点】：leftRoot.left.next = leftRoot.right;

然后 leftRoot = leftRoot.left;

而且 leftRoot 和 head肯定不止移动一次，所以需要循环。

最后返回 根结点 root 就行了。

这题就完成了！

代码如下

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

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/classSolution{publicNodeconnect(Node root){if(root ==null){return root;}Node leftRoot = root;while(leftRoot.left !=null){Node head = leftRoot;while(head !=null){
                head.left.next = head.right;if(head.next !=null){
                    head.right.next = head.next.left;}
                head = head.next;}
            leftRoot = leftRoot.left;}return root;}}

附图