本文主要是介绍leetcode117~Populating Next Right Pointers in Each Node II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Follow up for problem “Populating Next Right Pointers in Each Node”.
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
You may only use constant extra space.
For example,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
详细的解释过程在程序中。第二种解法比较简洁~关键在于引入了一个dummyNode节点。通常来说，二叉树中引入dummyNode节点是为了使二叉树中的所有节点都是处于同一个地位的，因为这时会使dummyNode节点的指针指向头节点。
本题中引入了dummyNode节点，使pre节点每次从dummyNode节点开始进行遍历，这样dummyNode节点的next指针会始终指向每一层的最左节点，省去了在程序中对最左节点的判断和查询过程。
public class PopulatingNextRightPointers117 {
/** 思路与上题类似，同样是在遍历上层节点时，去完成下一层节点的链接过程* 不同的是，这里只是一棵普通的二叉树了。首先在确定next节点的值时，需要对左右孩子都进行判断，找到最左节点* 其次，要判断是有左孩子还是右孩子，再进行相应的链接*/public void connect(TreeLinkNode root) {if(root==null) return;TreeLinkNode parent =root;//负责对每层节点进行遍历并链接TreeLinkNode pre;;//指向每层的最左节点TreeLinkNode next;;while(parent!=null) {pre = null;next = null;//对每层节点的遍历循环while(parent!=null) {//对next赋值if(next==null) {if(parent.left!=null) {next = parent.left;} else {//不管右孩子节点是否为空next = parent.right;}}if(parent.left!=null) {if(pre!=null) {//跨父节点进行链接pre.next = parent.left;pre = pre.next;} else {pre = parent.left;}}if(parent.right!=null) {if(pre!=null) {//同一个父节点的两个孩子进行链接pre.next = parent.right;pre = pre.next;} else {pre = parent.right;}}parent = parent.next;}parent = next;}}/** 引用一个节点dummyNode，使它的next节点指向最左节点，这样就不用去判断寻找最左节点* 一般来说，dummyNode的下一节点指向头节点，这样就能使二叉树中的所有节点（包括头节点）都是一样的，因为这样使头节点有了前驱*/public void connect2(TreeLinkNode root) {if(root == null) return ;TreeLinkNode parent = root;while(parent!=null) {TreeLinkNode dummyNode = new TreeLinkNode(-1);TreeLinkNode pre = dummyNode;while(parent!=null) {if(parent.left!=null) {pre.next = parent.left;pre = parent.left;}if(parent.right!=null) {pre.next = parent.right;pre = parent.right;}parent = parent.next;}parent = dummyNode.next;}}
}
这篇关于leetcode117~Populating Next Right Pointers in Each Node II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
