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

题目描述

题解

DFS

直观地分析, 对于每个节点root, 需要将其左节点的next指向其右节点即可. 但是这道题的关键在右节点的指向.

对于图中的节点5, 他是2的右儿子, 它指向的是3 的左儿子, 而3是2的next节点.

所以指代关系就出来了.

root.left.next = root.right;

root.right.next = root.next.left;

因为对每个节点进行处理时是已知该节点的next的指向的, 所以这道题要按照自顶向下的方法, 也就是先序遍历去做.

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

    Node left = root.left;
    Node right = root.right;

    if(left!=null){
        left.next = right;
    }

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

    connect(root.left);
    connect(root.right);

    return root;
}