数据结构与算法之二叉树: LeetCode 117. 填充每个节点的下一个右侧节点指针 II (Ts版)

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

• https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/

描述

• 给定一个二叉树：

  struct Node {
    int val;
    Node *left;
    Node *right;
    Node *next;
  }
  

• 填充它的每个 next 指针，让这个指针指向其下一个右侧节点
• 如果找不到下一个右侧节点，则将 next 指针设置为 NULL
• 初始状态下，所有 next 指针都被设置为 NULL

示例 1

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

示例 2

输入：root = []
输出：[]

提示

• 树中的节点数在范围 [0, 6000] 内
• -100 <= Node.val <= 100
• 进阶：
  • 你只能使用常量级额外空间
  • 使用递归解题也符合要求，本题中递归程序的隐式栈空间不计入额外空间复杂度

Typescript 版算法实现

1 ）方案1: 层次遍历

/**
 * Definition for _Node.
 * class _Node {
 *     val: number
 *     left: _Node | null
 *     right: _Node | null
 *     next: _Node | null
 * 
 *     constructor(val?: number, left?: _Node, right?: _Node, next?: _Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function connect(root: _Node | null): _Node | null {
    if (root === null) return null;
    const queue = [root];
    while (queue.length) {
        const n = queue.length;
        let last = null;
        for (let i = 1; i <= n; ++i) {
            let f = queue.shift();
            if (f.left !== null) queue.push(f.left);
            if (f.right !== null) queue.push(f.right);
            if (i !== 1) last.next = f;
            last = f;
        }
    }
    return root;
};

2 ）方案2: 使用已建立的 next 指针

/**
 * Definition for _Node.
 * class _Node {
 *     val: number
 *     left: _Node | null
 *     right: _Node | null
 *     next: _Node | null
 * 
 *     constructor(val?: number, left?: _Node, right?: _Node, next?: _Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

let last: Node | null = null;
let nextStart: Node | null = null;

/**
 * @param {Node} root
 * @return {Node}
 */
function connect(root: Node | null): Node | null {
    if (root === null) return null;

    let start: Node | null = root;

    while (start !== null) {
        last = null;
        nextStart = null;

        for (let p: Node | null = start; p; p = p.next) {
            if (p.left) handle(p.left);
            if (p.right) handle(p.right);
        }

        start = nextStart;
    }

    return root;
}

// 处理节点的函数
function handle(p: Node | null): void {
    if (last !== null) last.next = p;
    if (nextStart === null) nextStart = p;
    last = p;
}