跳至主要內容

Mr.He小于 1 分钟

/**
 * // Definition for a _Node.
 * function _Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {_Node} root
 * @return {_Node}
 */
var connect = function(root) {
    if (!root) return null; // 修正1: 空树返回 null

    const queue = [root];

    while (queue.length) {
        const levelSize = queue.length;

        for (let i = 0; i < levelSize; i++) {
            // 修正2: 在循环内部取出节点
            const node = queue.shift();

            // 核心逻辑:如果当前节点不是该层的最后一个节点,则连接到队列中的下一个节点
            // 队列中下一个节点 (queue[0]) 就是当前节点右侧的节点
            if (i < levelSize - 1) {
                node.next = queue[0];
            }
            // 如果是最后一个节点 (i === levelSize - 1),node.next 保持为 null (默认值),无需显式设置

            // 加入子节点
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }

    return root; // 修正3: 返回修改后的树根节点
};

定义功能函数

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if(root === null) return null
    connectTwo(root.left, root.right)
    return root
};

var connectTwo = function(left, right){
    if(left === null || right === null) return;

    left.next = right
    connectTwo(left.left, left.right)
    connectTwo(right.left, right.right)
		
		// 跨父节点链接
    connectTwo(left.right, right.left)
}