116. 填充二叉树的右侧指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
    int val;
    Node *left;
    Node *right;
    Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

参考前序遍历二叉树的实现

public static TreeNode connectNode(TreeNode node) {
    // 递归的结束条件
    if (node == null || node.left == null) {
        // 终止时处理办法
        return null;
    }
    // 当前节点需要做的事情
    nodeNeedTodo(node);
    // 让当前节点的左子节点重复当前节点
    connectNode(node.left);
    // 让当前节点的右子节点重复当前节点
    connectNode(node.right);
    return node;
}
/**
 * 让左子节点指向右子节点
 */
private static void nodeNeedTodo(TreeNode node) {
    node.left.next = node.right;
}

测试验证

public static void main(String[] args) {
    Integer[] arr = {4,2,7,1,3,6,9};
    TreeNode root = BinaryTreeUtil.arrToTree(arr);
    root = connectNode(root);
    BinaryTreeUtil.levelOrderPrintNext(root);
}

4-->null 2-->7 7-->null 1-->3 3-->null 6-->9 9-->null

正确的节点需要做的事

private static void nodeNeedTodo(TreeNode node1, TreeNode node2) {
    node1.next = node2
}

正确的算法

public static TreeNode connectNode(TreeNode node) {
    if (node == null) {
        return null;
    }
    connectNode(node.left, node.right);
    return node;
}
private static void connectNode(TreeNode node1, TreeNode node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    // 需要节点做的事情
    nodeNeedTodo(node1, node2);
    // 相同父节点
    // 左子树的左子节点指向右子节点
    connectNode(node1.left, node1.right);
    // 右子树的左子节点指向右子节点
    connectNode(node2.left, node2.right);
    // 跨父节点
    // 左子树的右子节点指向右子树的左子节点
    connectNode(node1.right, node2.left);
  }

测试验证

public static void main(String[] args) {
    Integer[] arr = {4,2,7,1,3,6,9};
    TreeNode root = BinaryTreeUtil.arrToTree(arr);
    root = connectNode(root);
    BinaryTreeUtil.levelOrderPrintNext(root);
}

4-->null 2-->7 7-->null 1-->3 3-->6 6-->9 9-->null

树节点对象

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode next;
    TreeNode(){}
    TreeNode(int val) {this.val = val;}
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

辅助工具类

/**
 * 层序遍历打印
 * @param node
 */
public static void levelOrderPrintNext(TreeNode node) {
    if (node == null) {
        return;
    }
    LinkedList<TreeNode> linkedList = new LinkedList<>();
    linkedList.add(node);
    while (!linkedList.isEmpty()) {
        TreeNode temp = linkedList.remove();
        if (temp.next == null) {
            System.out.print(temp.val + "-->" + temp.next + " ");
        } else {
            System.out.print(temp.val + "-->" + temp.next.val + " ");
        }
        if (temp.left != null) {
            linkedList.add(temp.left);
        }
        if (temp.right != null) {
            linkedList.add(temp.right);
        }
    }
}