`
blue2048
  • 浏览: 183609 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

[leetcode]Populating Next Right Pointers in Each Node II - java

阅读更多

这道题有个点,即使用空间来对树进行分层,这个点对于不完全二叉树还是很常见的技巧

/**

 * 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) {

        if(root == null){

            return;

        }

        LinkedList<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();

        LinkedList<TreeLinkNode> childQueue = new LinkedList<TreeLinkNode>();

        queue.add(root);

        TreeLinkNode preNode = null;

        while (!queue.isEmpty()){

            TreeLinkNode node = queue.remove();

            if(preNode != null){

                preNode.next=node;

            }

            preNode = node;

            if(node.left != null){

                childQueue.add(node.left);

            }

            if(node.right!=null){

                childQueue.add(node.right);

            }

            if(queue.isEmpty() && !childQueue.isEmpty()){

                queue.addAll(childQueue);

                childQueue.clear();

                preNode=null;

            }

        }

    }

}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics