Java for LeetCode 117 Populating Next Right Pointers in Each Node II
浏览数：233 /
时间：2015年06月08日
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
解题思路一：
本题的难点在于需要逐层遍历才行，因此可以用Java for LeetCode 102 Binary Tree Level Order Traversal的思路，JAVA实现如下：
public void connect(TreeLinkNode root) {
if (root == null || (root.left == null && root.right == null))
return;
List<List<TreeLinkNode>> list=new ArrayList<List<TreeLinkNode>>();
Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
queue.add(root);
while (queue.size() != 0) {
List<TreeLinkNode> alist = new ArrayList<TreeLinkNode>();
for (TreeLinkNode child : queue)
alist.add(child);
list.add(new ArrayList<TreeLinkNode>(alist));
Queue<TreeLinkNode> queue2=queue;
queue=new LinkedList<TreeLinkNode>();
for(TreeLinkNode child:queue2){
if (child.left != null)
queue.add(child.left);
if (child.right != null)
queue.add(child.right);
}
}
for(List<TreeLinkNode> alist:list)
for(TreeLinkNode aNode:alist)
connectARoot(aNode);
}
public static void connectARoot(TreeLinkNode root){
if (root == null || (root.left == null && root.right == null))
return;
if (root.next == null) {
if (root.left != null)
root.left.next = root.right;
}
else if (root.right == null) {
TreeLinkNode temp=root.next;
while(temp!=null){
if(temp.left==null&&temp.right==null)
temp=temp.next;
else break;
}
if(temp!=null)
root.left.next = (temp.left == null?temp.right:temp.left);
}else {
if (root.left != null)
root.left.next = root.right;
TreeLinkNode temp=root.next;
while(temp!=null){
if(temp.left==null&&temp.right==null)
temp=temp.next;
else break;
}
if(temp!=null)
root.right.next = (temp.left == null?temp.right:temp.left);
}
}
解题思路二：
不使用队列，请移步Populating Next Right Pointers in Each Node I II@LeetCode
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
