leetcode [116]Populating Next Right Pointers in Each Node

佚名 6年前 (2019-04-14) 随笔 1263人围观抢沙发百度已收录

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Initially, all next pointers are set to NULL.

题目大意：

就是将树的每一层的节点相互连接起来

解法：

我是按照层序遍历的方法，将每一层的节点指向当前队列的头结点，如果是该层的最后一个节点，则指向为空。

java:

class Solution {
    public Node connect(Node root) {
        if(root==null) return root;
        Deque<Node>q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int sz=q.size();
            for(int i=0;i<sz-1;i++){
                Node n=q.pop();
                n.next=q.peek();
                if(n.left!=null) q.add(n.left);
                if(n.right!=null) q.add(n.right);
            }
            Node n=q.pop();
            n.next=null;
            if(n.left!=null) q.add(n.left);
            if(n.right!=null) q.add(n.right);
        }

        return root;
    }
}

题目所给的是一个完全二叉树，那么除了叶子节点，其他节点的子节点都是两个子节点，可以在更改next指针的同时遍历二叉树，利用next指针完成层之间的遍历。

更好的java解法:

class Solution {
    public Node connect(Node root) {
        if(root==null) return root;
        Node pre=root;
        Node cur=null;
        while (pre.left!=null){
            cur=pre;
            while(cur!=null){
                cur.left.next=cur.right;
                if(cur.next!=null) cur.right.next=cur.next.left;
                cur=cur.next;
            }
            pre=pre.left;
        }

        return root;
    }
}