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

题目描述

思路

遍历思想(利用二叉树的先序遍历)

本题目的难点在于对于不同父节点的邻接问题因此我们可以抽象将两两节点为一组（不同父节点的两个孩子节点也抽象为一组），在此基础上再将两个节点连接起来
此题中，我门利用遍历思想（利用先序遍历）先将相同父节点的节点连接起来，再利用父节点将逻辑上抽象的节点练级起来（可能看起来不好懂，直接看代码）

复杂度

时间复杂度:

$O(n)$;其中$n$为二叉树的节点个数

空间复杂度:

$O(h)$；其中$h$为二叉树的高度

Code

/*
// 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 null;
        }
        traverse(root.left, root.right);
        return root;
    }

    
    private void traverse(Node node1, Node node2) {
        if (node1 == null || node1 == null) {
            return;
        }
        // Pre-order position
        // Connect the two input nodes;
        node1.next = node2;
        // Connect two child nodes with the same parent
        traverse(node1.left, node1.right);
        traverse(node2.left, node2.right);
        // Connect two child nodes across parent nodes 
        traverse(node1.right , node2.left);
    }
}