[LeetCode 117]Populating Next Right Pointers in Each Node II

题目链接：populating-next-right-pointers-in-each-node-ii

相同题型：Populating Next Right Pointers in Each Node

import java.util.LinkedList;/** * 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 7After calling your function, the tree should look like:1 -> NULL/ \2 -> 3 -> NULL/ \ \4-> 5 -> 7 -> NULL * */public class PopulatingNextRightPointersInEachNodeII {public class TreeLinkNode {int val;TreeLinkNode left, right, next;TreeLinkNode(int x) {val = x;}}//解法一 递归法//61 / 61 test cases passed.//Status: Accepted//Runtime: 290 ms//Submitted: 0 minutes ago//时间复杂度：O(n) 空间复杂度：O(1)public void connect(TreeLinkNode root) {if (root != null) {TreeLinkNode firstNode = null; //下一层的首个节点TreeLinkNode nextNode = null; //下一层已链接的尾节点while (root != null) {if (root.left != null) {if (firstNode == null) {firstNode = root.left;nextNode = firstNode;} else {nextNode.next = root.left;nextNode = nextNode.next;}}if (root.right != null) {if (firstNode == null) {firstNode = root.right;nextNode = firstNode;} else {nextNode.next = root.right;nextNode = nextNode.next;}}root = root.next;}connect(firstNode);}}//解法二 迭代法// 61 / 61 test cases passed.// Status: Accepted// Runtime: 271 ms// Submitted: 0 minutes ago //时间复杂度：O(n) 空间复杂度：O(1)public void connect1(TreeLinkNode root) {while (root != null) {TreeLinkNode firstNode = null; //下一层的首个节点TreeLinkNode nextNode = null; //下一层已链接的尾节点while (root != null) {if (root.left != null) {if (firstNode == null) {firstNode = root.left;nextNode = firstNode;} else {nextNode.next = root.left;nextNode = nextNode.next;}}if (root.right != null) {if (firstNode == null) {firstNode = root.right;nextNode = firstNode;} else {nextNode.next = root.right;nextNode = nextNode.next;}}root = root.next;}root = firstNode;}}// 解法三：层次遍历法// 61 / 61 test cases passed.// Status: Accepted// Runtime: 359 ms// Submitted: 0 minutes ago//时间复杂度：O(n) 空间复杂度：O(n)public void bfs(TreeLinkNode root) {if(root == null) {return;}LinkedList<TreeLinkNode> stack = new LinkedList<TreeLinkNode>();stack.add(root);while(!stack.isEmpty()) {int size = stack.size();for (int i = 0; i < size; i++) {TreeLinkNode node = stack.remove(0);node.next = (i == size – 1) ? null : stack.getFirst();if(node.left != null)stack.add(node);if(node.right != null)stack.add(node.right);}}}public static void main(String[] args) {// TODO Auto-generated method stub}}

，可见内心底对旅行是多么的淡漠。