欢迎访问LeetCode题解合集

题目描述

给定一个二叉树

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

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

进阶：

• 你只能使用常量级额外空间。
• 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

[HTML_REMOVED]

[HTML_REMOVED]

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

• 树中的节点数小于 6000
• $-100 \le node.val \le 100$

题解：

参考 填充每个节点的下一个右侧节点指针 ，上题是 完美二叉树 ，而本题是一般二叉树，稍微麻烦一点。。。

本题从连接 相邻节点 变为 下一个非空节点。

法一：

广搜。

将同一层的节点通过 next 指针连接起来。需要一次处理同一层所有节点。

注意：广搜从右往左好写一些。

时间复杂度：$O(n)$

额外空间复杂度：$O(n)$

class Solution {
public:
    Node* connect(Node* root) {
        if ( !root ) return root;
        queue<Node*> q;
        q.push( root );
        int i, size;
        Node *pre = NULL, *now = NULL;

        while ( q.size() ) {
            size = q.size();
            pre = NULL;
            for ( i = 0; i < size; ++i ) {
                now = q.front();
                q.pop();
                now->next = pre;
                pre = now;
                if ( now->right ) q.push( now->right );
                if ( now->left ) q.push( now->left );
            }
        }

        return root;
    }
};
/*
时间：8ms，击败：99.13%
内存：17.1MB，击败：73.56%
*/

法二：

方法一 中没有利用 next 指针，接下来考虑利用 next 指针。

还是按层来考虑，每层从最左边节点开始：

• 对于每个节点，让左儿子的 next 指向右儿子，然后让右儿子的 next 指向下一个节点的左儿子，同层之间通过 next 移动到下一个节点。
• 直到最后一层停止

每次处理当前层时，下一层的节点已经通过 next 指针连接在一起，所以可以利用 next 指针在同层之间进行移动。

注意：此题每层找第一个非空节点比较麻烦，可以考虑建一个 哨兵节点 。

时间复杂度：$O(n)$

额外空间复杂度：$O(1)$

class Solution {
public:
    Node* connect(Node* root) {
        if ( !root ) return root;
        Node dummy;
        Node *head = &dummy;
        Node *tail = NULL, *now = root;
        while ( now ) {
            tail = head;
            while ( now ) {
                if ( now->left ) {
                    tail->next = now->left;
                    tail = tail->next;
                }
                if ( now->right ) {
                    tail->next = now->right;
                    tail = tail->next;
                }
                now = now->next;
            }
            if ( tail == head ) break;
            now = head->next;
        }
        return root;
    }
};
/*
时间：12ms，击败：92.24%
内存：16.9MB，击败：97.43%
*/

法三：

方法二 的 先序遍历 实现。

注意：需要先递归右子树，否则上级节点的 next 关系没建立好，下级没法找到下一个非空节点。

时间复杂度：$O(n)$

额外空间复杂度：$O(h)$ ，$h$ 是树的高度。

class Solution {
public:
    Node* getNext( Node* root ) {
        Node *p = root->next;
        while ( p ) {
            if ( p->left ) return p->left;
            if ( p->right ) return p->right;
            p = p->next;
        }
        return NULL;
    }
    void dfs( Node* root ) {
        if ( !root ) return;
        if ( root->left && root->right ) {
            root->left->next = root->right;
            root->right->next = getNext( root );
        } else if ( root->left ) {
            root->left->next = getNext( root );
        } else if ( root->right ) {
            root->right->next = getNext( root );
        }
        dfs( root->right );
        dfs( root->left );
    }
    Node* connect(Node* root) {
        dfs( root );
        return root;
    }
};
/*
时间：12ms，击败：92.24%
内存：16.8MB，击败：98.25%
*/