給定一個二叉樹

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。

初始狀態下，所有 next 指針都被設置為 NULL。

進階：

你只能使用常量級額外空間。
使用遞歸解題也符合要求，本題中遞歸程序占用的棧空間不算做額外的空間復雜度。

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