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

难度: 🌕

问题描述

---

解法 1 - 层序

/*
// 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;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        // 思路：
        // 层序 - 辅助 队列
        if(root == null) {
            return root;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int len = queue.size();
            Node pre = null;
            for(int i = 0; i < len; i ++) {
                Node cur = queue.poll();
                if(pre != null) {
                    pre.next = cur;
                }
                pre = cur;
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        return root;
    }
}

---

输出 1

---

解法 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;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        // 思路：
        // 递归
        // 由于为完美二叉树，所有叶子节点在同一层，可以利用这一点
        return mySol(root);
    }

    private Node mySol(Node root) {
        // 递归终止条件
        if(root == null) {
            return root;
        }
        if(root.left != null) {
            // 由于叶子节点在同一层，那么左子树非空，意味着右子树也必定非空
            root.left.next = root.right;
            // 判断是否为最右侧节点
            if(root.next != null) {
                root.right.next = root.next.left;
            }
            mySol(root.left);
            mySol(root.right);
        }
        return root;
    }
}

---

输出 2