星空网 > 软件开发 > Java

116. 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
代码如下:
 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 public class Solution {10   public void connect(TreeLinkNode root) {11     int a=1;12     int b=a;13     List<TreeLinkNode> list=LevelTraverse(root);14    15     try{16     int i=0;17     while(i<list.size())18     {19     TreeLinkNode node=list.get(i);20     i++;21     b=b-1;22     while(b>0)23     {24         node.next=list.get(i);25         i++;26         node=node.next;27         b--;28     }29     node.next=null;30     b=a*2;31     a=b;32     }33     }catch(NullPointerException e){}34     35   }36   public ArrayList<TreeLinkNode> LevelTraverse(TreeLinkNode root)//树的水平遍历37   {38     ArrayList<TreeLinkNode> list=new ArrayList<TreeLinkNode>();39     Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();40     queue.add(root);41     try{42     while(queue.size()>0)43     {44       TreeLinkNode a=(TreeLinkNode)queue.peek();45       queue.remove();46       list.add(a);47       if(a.left!=null)48       queue.add(a.left);49       if(a.right!=null)50       queue.add(a.right);51     }52     }catch(NullPointerException e){}53  54     return list;55   }56 }

 




原标题:116. Populating Next Right Pointers in Each Node

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

南京到东海物流专线:https://www.goluckyvip.com/tag/97958.html
一键退税:https://www.goluckyvip.com/tag/9796.html
南京到三亚物流专线:https://www.goluckyvip.com/tag/97960.html
南宁到越南物流专线:https://www.goluckyvip.com/tag/97961.html
东莞到越南河内物流专线:https://www.goluckyvip.com/tag/97962.html
东莞到越南河内专线物流:https://www.goluckyvip.com/tag/97963.html
2022世界杯门票如何买?:https://www.vstour.cn/a/363182.html
沈阳到本溪的距离有多远?(详细路线及交通方式):https://www.vstour.cn/a/363183.html
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流