首页 > 代码库 > Populating Next Right Pointers in Each Node
Populating Next Right Pointers in Each Node
Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL
.
Initially, all next pointers are set to NULL
.
Note:
- You may only use constant extra space.
- You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1 / 2 3 / \ / 4 5 6 7
After calling your function, the tree should look like:
1 -> NULL / 2 -> 3 -> NULL / \ / 4->5->6->7 -> NULL
这道题提示说要用DFS,但我觉得用BFS好一点,这里我BFS将每一层的所有结点放到一个list中,然后将其放到queue中(这里后面觉得其实没有什么必要,不太想优化了),遍历list中所有元素node,如果node有左子树,将左右结点放到新的list中,遍历完原来的list,在把新的添加到queue中,这里queue作用不太大
1 /** 2 * Definition for binary tree with next pointer. 3 * public class TreeLinkNode { 4 * int val; 5 * TreeLinkNode left, right, next; 6 * TreeLinkNode(int x) { val = x; } 7 * } 8 */ 9 10 11 import java.util.ArrayList;12 import java.util.LinkedList;13 import java.util.List;14 import java.util.Queue;15 16 17 public class Solution {18 public void connect(TreeLinkNode root) {19 if(root == null) //如果root为空,直接返回20 return;21 else if(null == root.left && null == root.right){ //只有根节点22 root.next = null;23 }24 else{25 Queue<List<TreeLinkNode>> queue = new LinkedList<List<TreeLinkNode>>(); //队列,用于BFS 26 root.next = null; //设置root的next27 List<TreeLinkNode> element = new ArrayList<TreeLinkNode>();28 element.add(root.left); //左右子节点放到list中,list放到队列中29 element.add(root.right);30 31 queue.add(element);32 //boolean isEnd = false;33 34 while(!queue.isEmpty()){ //队列不为空35 List<TreeLinkNode> tempList = queue.poll(); //出队36 List<TreeLinkNode> newElement = null;37 38 if(tempList.get(0).left != null){ //有下一层时,在生成新的list39 newElement = new ArrayList<TreeLinkNode>();40 }41 for(int i = 0 ; i < tempList.size() - 1; i++){ //遍历该层所有节点42 TreeLinkNode preNode = tempList.get(i);43 TreeLinkNode behind = tempList.get(i + 1);44 45 preNode.next = behind; //设置next属性46 if(preNode.left != null){47 newElement.add(preNode.left); //下一层的节点放到list中48 newElement.add(preNode.right);49 } 50 }51 52 //同一层最后一个结点单独设置53 TreeLinkNode last = tempList.get(tempList.size() - 1);54 last.next = null;55 56 if(null != newElement && null != last.left){57 newElement.add(last.left);58 newElement.add(last.right);59 //将list放到队列中60 queue.add(newElement);61 } 62 }63 }64 }65 }
在DISCUSS有个写的很PL的
1 void connect(TreeLinkNode *root) { 2 if (root == NULL) return; 3 TreeLinkNode *pre = root; 4 TreeLinkNode *cur = NULL; 5 while(pre->left) { 6 cur = pre; 7 while(cur) { 8 cur->left->next = cur->right; 9 if(cur->next) cur->right->next = cur->next->left;10 cur = cur->next;11 }12 pre = pre->left;13 }14 }
Populating Next Right Pointers in Each Node
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。