117. 填充每个节点的下一个右侧节点指针 II
给定一个二叉树

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

 

解析

比满二叉树要麻烦，一定要找到下个节点的位置。

注意点就是要先去递归右子树，因为我们的next都是往右边算的，如果右边没算完会很麻烦。

class Solution {
    public Node connect(Node root) {
        if(root==null) return null;
        if(root.left!=null){
            if(root.right!=null){
                root.left.next = root.right;
            }else{
                root.left.next = nextNode(root.next);
            }
        }
        if(root.right!=null){
            root.right.next = nextNode(root.next);
        }
        connect(root.right);
        connect(root.left);
        return root;
    }
    public Node nextNode(Node node){
        while(node!=null){
            if(node.left!=null) return node.left;
            if(node.right!=null) return node.right;
            node = node.next;
        }
        return null;
    }
}

注意：本文归作者所有，未经作者允许，不得转载