117. Populating Next Right Pointers in Each Node II（js）

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

117. Populating Next Right Pointers in Each Node II

Given a binary tree

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

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.
题意：当树不是完全二叉树时，给每个节点加一个next指针指向右方的节点
代码如下：

/**
 * Definition for binary tree with next pointer.
 * function TreeLinkNode(val) {
 *     this.val = val;
 *     this.left = this.right = this.next = null;
 * }
 */

/**
 * @param {TreeLinkNode} root
 * @return {void} Do not return anything, modify tree in-place instead.
 */
var connect = function(root) {
    if(!root)
        return null;
    let head = root;
    let dummy = new Node();
    while(root) {
        let currChild = dummy;
        while(root) {
            if(root.left) {
                currChild.next = root.left;
                currChild = currChild.next;
            }
            if(root.right) {
                currChild.next = root.right;
                currChild = currChild.next;
            }
            root = root.next;
        }
        root = dummy.next;
        dummy.next = null;
    }
    return head;
};