首页 > 代码库 > [LeetCode]116 Populating Next Right Pointers in Each Node
[LeetCode]116 Populating Next Right Pointers in Each Node
https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/
http://blog.csdn.net/linhuanmars/article/details/23499383
/** * Definition for binary tree with next pointer. * public class TreeLinkNode { * int val; * TreeLinkNode left, right, next; * TreeLinkNode(int x) { val = x; } * } */ public class Solution { public void connect(TreeLinkNode root) { // Solution A: connect_NoExtraSpace(root); // Solution B: // connect_ExtraSpace(root); } /////////////////////////// // Solution A: No Extra Space // private void connect_NoExtraSpace(TreeLinkNode root) { if (root == null) return; // Use a int maintain how many nodes in this level int nextlevelnodes = 0; int curlevelnodes = 1; TreeLinkNode pre = null; Queue<TreeLinkNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeLinkNode node = queue.poll(); curlevelnodes --; if (pre != null) pre.next = node; if (node.left != null) { nextlevelnodes ++; queue.offer(node.left); } if (node.right != null) { nextlevelnodes ++; queue.offer(node.right); } if (curlevelnodes == 0) { // this is the last nodes of that level // Start a new level. pre = null; curlevelnodes = nextlevelnodes; nextlevelnodes = 0; } else { pre = node; } } } /////////////////////////// // Solution B: Extra Space // private void connect_ExtraSpace(TreeLinkNode root) { if (root == null) return; // BFS. List<List<TreeLinkNode>> levels = new ArrayList<>(); Queue<LevelNode> queue = new LinkedList<>(); queue.offer(new LevelNode(root, 1)); while (!queue.isEmpty()) { LevelNode levelNode = queue.poll(); // Add one more level if needed if (levels.size() < levelNode.level) { levels.add(new ArrayList<TreeLinkNode>()); } levels.get(levelNode.level - 1).add(levelNode.node); if (levelNode.node.left != null) { queue.offer(new LevelNode(levelNode.node.left, levelNode.level + 1)); } if (levelNode.node.right != null) { queue.offer(new LevelNode(levelNode.node.right, levelNode.level + 1)); } } for (List<TreeLinkNode> list : levels) { for (int i = 0 ; i < list.size() ; i ++) { TreeLinkNode nextNode = i == list.size() - 1 ? null : list.get(i + 1); list.get(i).next = nextNode; } } } private static class LevelNode { private TreeLinkNode node; private int level; LevelNode(TreeLinkNode node, int level) { this.node = node; this.level = level; } } }
[LeetCode]116 Populating Next Right Pointers in Each Node
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。