You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Example:
网上找到比较好的讲解是来自 https://segmentfault.com/a/1190000003465911
1. 先来递归的
由于父节点多了next指针，我们不用记录父节点的父节点就能直到它相邻的节点。对于左子节点来说，其next节点就是父节点的右节点。对于右子节点来说i，其next节点就是父节点的next节点的左子节点。以此递归。
// Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} 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) { Node level_start=root; while(level_start!=null){ Node cur=level_start; while(cur!=null){ if(cur.left!=null) cur.left.next=cur.right; if(cur.right!=null && cur.next!=null) cur.right.next=cur.next.left; cur=cur.next; } level_start=level_start.left; } return root; } }
116. Populating Next Right Pointers in Each Node
原文：https://www.cnblogs.com/wentiliangkaihua/p/10509641.html