GVKun编程网logo

[LeetCode] 116. Populating Next Right Pointers in Each Node 每个节点的右向指针

214

在这篇文章中，我们将带领您了解[LeetCode]116.PopulatingNextRightPointersinEachNode每个节点的右向指针的全貌，同时，我们还将为您介绍有关(Java)Le

在这篇文章中，我们将带领您了解[LeetCode] 116. Populating Next Right Pointers in Each Node 每个节点的右向指针的全貌，同时，我们还将为您介绍有关(Java) LeetCode 116. Populating Next Right Pointers in Each Node —— 填充同一层的兄弟节点、116. Populating Next Right Pointers in Each Node、117. Populating Next Right Pointers in Each Node II、117. Populating Next Right Pointers In Each NodeII的知识，以帮助您更好地理解这个主题。

本文目录一览：

[LeetCode] 116. Populating Next Right Pointers in Each Node 每个节点的右向指针

[LeetCode] 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

给定一棵二叉树，有一个next指针，将它们的每一层链接起来。只能使用常量额外空间，树是一棵完美二叉树。

将树的每一层节点用next串起来。这样每一层也会形成一个单链表。而每层的链表头，则是根的左孩子。利用双循环，外层循环，沿着根的左孩子，一直向下。内层循环，负责将下一层的节点串起来。即将自己右孩子放到左孩子的next上，而右孩子，则可通过自己的next指针，找到右邻居。 

解法1: 递归

解法2: 迭代

Java: T: O(n), S: O(1)

public class Solution {
    public void connect(TreeLinkNode root) {
        TreeLinkNode level_start=root;
        while(level_start!=null){
            TreeLinkNode cur=level_start;
            while(cur!=null){
                if(cur.left!=null) cur.left.next=cur.right;
                if(cur.right!=null && cur.next!=null) cur.right.next=cur.next.left;
                
                cur=cur.next;
            }
            level_start=level_start.left;
        }
    }
}　　

Java:

public class Solution {

    public void connect(TreeLinkNode root) {

        TreeLinkNode node;
        // 题中假设了输入的树是一棵完全叉树
        // 第一个循环用来处理整个树
        // root.left != null如果不用，则处理到最后第一个没有左右子树的结点会出错
        while (root != null && root.left != null) {
            // 每个root表示第一个层的第一个结点
            // node记录每一个层的第一个结点
            node = root;

            // 处理每个层
            while (node != null) {
                // 表示连接的是同一个结点的下的两子结点
                node.left.next = node.right;
                // node不是某个层的最后一个结点
                if (node.next != null) {
                    // 将这个结点的右子结点连接到这个结点的同层相邻结点的左子结点上
                    node.right.next = node.next.left;
                }

                // 移动到同层的下一个结点
                node = node.next;
            }

            // 移动到下一层的第一个结点
            root = root.left;
        }

    }
}

Python: Time: O(n), Space: O(1)

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None
    
    def __repr__(self):
        if self is None:
            return "Nil"
        else:
            return "{} -> {}".format(self.val, repr(self.next))

class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
        head = root
        while head:
            prev, cur, next_head = None, head, None
            while cur and cur.left:
                cur.left.next = cur.right
                if cur.next:
                    cur.right.next = cur.next.left
                cur = cur.next
            head = head.left

Python: Recursion, Time: O(n), Space: O(logn)

class Solution:
    # @param root, a tree node
    # @return nothing
    def connect(self, root):
        if root is None:
            return
        if root.left:
            root.left.next = root.right
        if root.right and root.next:
            root.right.next = root.next.left
        self.connect(root.left)
        self.connect(root.right)

C++:

void connect(TreeLinkNode *root) {
    if (root == NULL) return;
    TreeLinkNode *pre = root;
    TreeLinkNode *cur = NULL;
    while(pre->left) {
        cur = pre;
        while(cur) {
            cur->left->next = cur->right;
            if(cur->next) cur->right->next = cur->next->left;
            cur = cur->next;
        }
        pre = pre->left;
    }
}　　

C++:  Recursion, more than constant space

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        if (root->left) root->left->next = root->right;
        if (root->right) root->right->next = root->next? root->next->left : NULL;
        connect(root->left);
        connect(root->right);
    }
};

C++: Non-recursion, more than constant space

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        queue<TreeLinkNode*> q;
        q.push(root);
        q.push(NULL);
        while (true) {
            TreeLinkNode *cur = q.front();
            q.pop();
            if (cur) {
                cur->next = q.front();
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            } else {
                if (q.size() == 0 || q.front() == NULL) return;
                q.push(NULL);
            }
        }
    }
};　　

C++: 用两个指针start和cur，其中start标记每一层的起始节点，cur用来遍历该层的节点

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode *start = root, *cur = NULL;
        while (start->left) {
            cur = start;
            while (cur) {
                cur->left->next = cur->right;
                if (cur->next) cur->right->next = cur->next->left;
                cur = cur->next;
            }
            start = start->left;
        }
    }
};

 

类似题目：

[LeetCode] 117. Populating Next Right Pointers in Each Node II 每个节点的右向指针 II

 

All LeetCode Questions List 题目汇总

 

(Java) LeetCode 116. Populating Next Right Pointers in Each Node —— 填充同一层的兄弟节点

(Java) LeetCode 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.
  • Recursive approach is fine, implicit stack space does not count as extra space for this problem.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

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

 

这里递归不算extra space，那么先试试看递归解法。

对于第一层只有root（如果其存在），那么需要看它的左孩子是否存在。如果存在，那么它的next一定等于root的右孩子，不论右孩子存不存在。而对于右孩子，仅仅对于第一层root来说，这一步不用做任何事，只不过如果root右孩子存在，那么此时它已经被连接到root左孩子的next上，而且它本身的next初始为null。这样继续递归调用下一层的节点时候，同样的左孩子如果存在，其next连到右孩子。而这时候要判断此时根节点的next是否为null。如果不为null，相当于此时根节点存在同层的兄弟节点，且这个兄弟节点已经存在当前递归节点的next域中。那么，如果这时根节点的右孩子也存在的话，它是一定等于根节点的兄弟节点的左孩子，不论其左孩子是否为空。之后递归调用每一层根节点的左右孩子即可。看上去很绕，但原理是每一次连上一个根节点的左右孩子，这样下一层时候就知道了兄弟节点是否存在，以便于继续链接根节点及其兄弟节点的孩子。

 

对于迭代，如果不需要常数空间复杂度的话，可以利用队列将每一层的节点存起来，之后逐个处理next域。如果要求常数复杂度，那么就需要在每一层增加一个指针node，从最左边遍历到最右边，逐个将节点连接起来。遍历的方法和递归的想法一样，还是利用上一层next已经连接起来的结果，通过父节点的next域移动到兄弟节点的子节点。

 

解法一，递归（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;
        if (root.left != null) root.left.next = root.right;
        if (root.next != null && root.right != null) root.right.next = root.next.left;
        connect(root.left);
        connect(root.right);     
    }
}

 

解法二，迭代，非常数空间（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;
        Queue<TreeLinkNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeLinkNode t = q.poll();
                if (i < size - 1)
                    t.next = q.peek();
                if (t.left != null) q.add(t.left);
                if (t.right != null) q.add(t.right);
            } 
        }
    }
}

 

解法三，迭代，常数空间（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;
        TreeLinkNode pre = root;
        while (pre.left != null) {
            TreeLinkNode 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;
        }    
    }
}

 

116. Populating Next Right Pointers in Each Node

116. Populating Next Right Pointers in Each Node

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.
Initially, all next pointers are set to NULL.
Example:

Input: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:
You may only use constant extra space.
Recursive approach is fine, implicit stack space does not count as extra space for this problem.

难度：medium

题目：给定一满二叉树，所有叶结点在同一层，每个结点都有左右子树。

思路：自上至下自左至右遍历

Runtime: 0 ms, faster than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node.
Memory Usage: 36.1 MB, less than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node.

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val,Node _left,Node _right,Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
    public Node connect(Node root) {
        Node ptr = root;
        while (ptr != null) {
            Node head = ptr, rightMost = null;
            ptr = ptr.left;
            while (head != null && head.left != null) {
                if (rightMost != null) {
                    rightMost.next = head.left;
                }
                head.left.next = head.right;
                rightMost = head.right;
                head = head.next;
            }
        }
        
        return root;
    }
}

117. Populating Next Right Pointers in Each Node II

117. Populating Next Right Pointers in Each Node II

Given a binary tree

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.

Initially, all next pointers are set to NULL.

Example:

Input: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":null,"next":null,"right":{"$id":"6","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}

Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:

1. You may only use constant extra space.
2. Recursive approach is fine, implicit stack space does not count as extra space for this problem.

难度：medium

题目：给定二叉树，计算结点指向其相邻右结点的下一跳指针。如果没有相邻的右结点则next为NULL.

思路：递归

Runtime: 3 ms, faster than 18.40% of Java online submissions for Populating Next Right Pointers in Each Node II.
Memory Usage: 51.8 MB, less than 100.00% of Java online submissions for Populating Next Right Pointers in Each Node II.

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val,Node _left,Node _right,Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
class Solution {
    public Node connect(Node root) {
        Node ptr = root;
        while (ptr != null) {
            ptr = buildNodeNext(ptr);
        }
        
        return root;
    }
    
    private Node buildNodeNext(Node head) {
        if (null == head) {
            return null;
        }
        Node nextLevelLeftMost = buildNodeNext(head.next);
        Node left = head.left;
        Node right = head.right;
        if (left != null && right != null) {
            left.next = right;
            right.next = nextLevelLeftMost;
            return left;
        }
        
        if (left != null && right == null) {
            left.next = nextLevelLeftMost;
            return left;
        } 
        
        if (left == null && right != null) {
            right.next = nextLevelLeftMost;
            return right;
        }
        
        return nextLevelLeftMost;
    }
}

117. Populating Next Right Pointers In Each NodeII

117. Populating Next Right Pointers In Each NodeII

题目：
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,

     1
   /  \
  2    3
 / \    \
4   5    7

After calling your function, the tree should look like:

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

解答：

public class Solution {
    public void connect(TreeLinkNode root) {
        //重点是记录current, head, prev这三个结点
        TreeLinkNode curt = root;
        TreeLinkNode head = null;
        TreeLinkNode prev = null;
        
        while (curt != null) {
            while (curt != null) {
                if (curt.left != null) {
                    if (prev != null) {
                        prev.next = curt.left;
                    } else {
                        head = curt.left;
                    }
                    prev = curt.left;
                }
                if (curt.right != null) {
                    if (prev != null) {
                        prev.next = curt.right;
                    } else {
                        head = curt.right;
                    }
                    prev = curt.right;
                }
                curt = curt.next;
            }
            curt = head;
            head = null;
            prev = null;
        }
    }
}

今天关于[LeetCode] 116. Populating Next Right Pointers in Each Node 每个节点的右向指针的介绍到此结束，谢谢您的阅读，有关(Java) LeetCode 116. Populating Next Right Pointers in Each Node —— 填充同一层的兄弟节点、116. Populating Next Right Pointers in Each Node、117. Populating Next Right Pointers in Each Node II、117. Populating Next Right Pointers In Each NodeII等更多相关知识的信息可以在本站进行查询。

本文标签：

上一篇在 ThinkPHP 框架（5.0.24）下引入 Ueditor 并实现向七牛云对象存储上传图片同时将图片信息保存到 MySQL 数据库，同时实现 lazyload 懒加载

下一篇type、object、class之间的关系（type和object关系很难理解）

相关文章