今天學(xué)習(xí)的是上篇算法的升級(jí)版：填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針Ⅱ。

題目介紹

給定任意一個(gè)二叉樹，填充它的next節(jié)點(diǎn)，指向下一個(gè)右側(cè)節(jié)點(diǎn)，最右側(cè)節(jié)點(diǎn)指向null。

看下圖吧：

二叉樹-填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針Ⅱ-題目.png

實(shí)現(xiàn)思路

直接看下圖吧：

二叉樹-填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針Ⅱ-解題.png

題目的解題思路和滿二叉樹的是類似的。

核心的邏輯是：
1、右節(jié)點(diǎn)不為空時(shí)，左節(jié)點(diǎn)的next為右節(jié)點(diǎn)；右節(jié)點(diǎn)為空時(shí)，左節(jié)點(diǎn)的next為父節(jié)點(diǎn)的next節(jié)點(diǎn)的左節(jié)點(diǎn)。依此類推，直到為null為止。
2、右節(jié)點(diǎn)和左節(jié)點(diǎn)是一樣的邏輯。

實(shí)現(xiàn)代碼

public 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;
    }
}

public class SolutionConnect2 {

    public Node connect(Node root) {
        if (null == root) {
            return null;
        }

        if (null != root.left) {
            if (null != root.right) {
                root.left.next = root.right;
            } else{
                root.left.next = connectRightNext(root);
            }
            connect(root.left);
        }

        if (null != root.right) {
            root.right.next = connectRightNext(root);
            connect(root.right);
        }
        return root;
    }

    private Node connectRightNext(Node root){
        Node next = root.next;
        while (null != next) {
            if (null != next.left) {
                next = root.left;
                break;
            } else if (null != next.right) {
                next = next.right;
                break;
            }
            next = next.next;
        }
        return next;
    }

}

算法相關(guān)實(shí)現(xiàn)源碼地址：https://github.com/xiekq/rubs-algorithms