LeetCode - 117 - 填充每个节点的下一个右侧节点指针 II - Java

文章目录

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

题目解析

给我们一棵普通树【非完全二叉树，也就是说：如果一个根结点的右子树不为null，并不能代表 它大的左子树 不为null】，这不是填充每个节点的下一个右侧节点指针I.
让我们将其使用孩子兄弟法来表示。

思维一： 队列 - 层序遍历

代码如下

/*
// 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){
                    tmp.next = queue.peek();}if(tmp.left !=null){
                    queue.offer(tmp.left);}if(tmp.right !=null){
                    queue.offer(tmp.right);}}}return root;}}

思维二： 将二叉树 看作 logN 个链表的组合

下面是这种做法的关键。

代码如下

classSolution{publicNodeconnect(Node root){if(root ==null){return root;}// 将cur 当 一个链表Node cur = root;while(cur!=null){// 在遍历当层的时候，将下一层的节点连接起来。// 为了方便操作，使用了一傀儡节点Node dummy =newNode();// 每一层的起始节点 的 前一个节点。Node  pre = dummy;while( cur !=null){// 遍历当前 cur 层的节点if(cur.left !=null){// 如果 cur.left 不为空 pre的下一个节点 就是 cur.left// 也就说将它们串起来【填充next值】
                    pre.next = cur.left;// pre 移动，为下一次链接做准备
                    pre = pre.next;}if(cur.right !=null){// 如果 cur.right 不为空 pre的下一个节点 就是 cur.right// 也就说将它们串起来【填充next值】
                    pre.next = cur.right;// pre 移动，为下一次链接做准备
                    pre = pre.next;}// cur 移动，访问这一行的下一个节点。
                cur =cur.next;}// 前面说到 dummy 是 下一层节点的 起始位置 的 傀儡节点// 它的next指向的节点，就是 cur 下一层的遍历的起始位置
            cur = dummy.next;}return root;}}

有兴趣的可以点进去看看

LeetCode所有的链表题的题解都这里哦，除了vip 和 关于 Hash 的题外，几乎都在里面。 二叉树、排序、堆，栈，队列 的题，正在一步步完善。