leetcode刷题记录 填充每个节点的下一个右侧节点指针

leetcode 填充每个节点的下一个右侧节点指针

解题思路： 1.层次遍历，此方法效率一般，但可以解决此题。 代码：

public Node connect(Node root) { if(root==null) return null; Queue<Node> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){ int len = queue.size(); Node right = null;//用于保存右结点,每一行的结点重置 for(int i = 0;i<len;i++){ Node cur = queue.poll(); if(cur.right!=null){ queue.add(cur.right); } if(cur.left!=null){ queue.add(cur.left); } //从右往左连接结点 cur.next = right; right = cur; } } return root; } }

我们可以优化下上面的代码，我们这里牺牲了效率，所以我们可以不使用队列，直接用两个结点来进行上面的操作。一个结点pre用来访问下一层左子结点，一个结点cur用来连接每一层的结点。

class Solution { public Node connect(Node root) { if(root==null){ return null; } 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; } }