Populating Next Right Pointers in Each Node II LeetCode[通俗易懂]

全栈程序员-站长 • 2022年1月29日上午8:00 • 未分类 • 阅读 37

大家好，又见面了，我是全栈君。

Populating Next Right Pointers in Each Node II

Total Accepted: 18934
Total Submissions: 62031
My Submissions

Follow up for problem “Populating Next Right Pointers in Each Node“.

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

You may only use constant extra space.

For example,
Given the following binary tree,

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

Have you been asked this question in an interview?

/**
 * 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 ;
        }
        Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int qSize = queue.size();
            TreeLinkNode preNode = null;
            for (int i = 0; i < qSize; i++){
                TreeLinkNode curNode = queue.poll();
                curNode.next = preNode;
                preNode = curNode;
                if (curNode.right != null){
                    queue.offer(curNode.right);
                }
                if (curNode.left != null){
                    queue.offer(curNode.left);
                }
            }
        }
    }
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115891.html原文链接：https://javaforall.net