leetcode:116. 填充每个节点的下一个右侧节点指针

题目

给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

  1. struct Node {
  2. int val;
  3. Node *left;
  4. Node *right;
  5. Node *next;
  6. }

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

示例 1:
[中等] 116. 填充每个节点的下一个右侧节点指针 - 图1

  1. 输入:root = [1,2,3,4,5,6,7]
  2. 输出:[1,#,2,3,#,4,5,6,7,#]
  3. 解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。

示例 2:

输入:root = []
输出:[]

解答 & 代码

解法一:BFS 层序遍历

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

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL)
            return root;

        queue<Node*> nodeQ;
        nodeQ.push(root);
        while(!nodeQ.empty())
        {
            int levelSize = nodeQ.size();
            for(int i = 0; i < levelSize; ++i)
            {
                Node* cur = nodeQ.front();
                nodeQ.pop();
                // 填充当前节点的 next 指针
                // - 如果当前节点不是这一层的最后一个节点,则将 next 指向其右侧节点
                // - 否则,当前节点是这一层的最后一个节点,next 设为 NULL
                cur->next = i == levelSize - 1 ? NULL : nodeQ.front();
                if(cur->left != NULL)
                    nodeQ.push(cur->left);
                if(cur->right != NULL)
                    nodeQ.push(cur->right);
            }
        }
        return root;
    }
};

复杂度分析:设二叉树共 N 个节点

  • 时间复杂度 O(N):遍历每个节点一次
  • 空间复杂度 O(N):队列 nodeQ 中存储的节点个数不会超过 N

执行结果:

执行结果:通过

执行用时:28 ms, 在所有 C++ 提交中击败了 6.31% 的用户
内存消耗:16.6 MB, 在所有 C++ 提交中击败了 44.29% 的用户

解法二:DFS

题目要将每层的节点都串成一个链表。

如何将题目的要求细化成每个节点需要做的事情

  • 如果 DFS 函数只传入一个节点 **root**,我们只能让它的左子节点指向右子节点,但不能让 root 的右子节点指向 root 的兄弟节点的左子节点。也就是说,无法连接不同父节点的两个相邻节点
  • 解决办法:DFS 函数传入两个相邻节点
  • 题目的要求就细化成了:将每两个相邻节点都连接起来 ```cpp / // Definition for a Node. class Node { public: int val; Node left; Node right; Node next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node _left, Node _right, Node* _next)

      : val(_val), left(_left), right(_right), next(_next) {}
    

    }; */

class Solution { private: // DFS,传入两个相邻节点 root1 和 root2,递归将这两棵树的相邻节点都连接起来 void connectTwoNode(Node root1, Node root2) { // 递归结束条件:有一个节点为 NULL,说明当前已在最后一层(完美二叉树),不用再往下层递归 if(root1 == NULL || root2 == NULL) return;

    // 前序位置:连接传入的两个节点
    root1->next = root2;
    // 递归
    // 连接相同父节点的两个相邻节点
    connectTwoNode(root1->left, root1->right);
    connectTwoNode(root2->left, root2->right);
    // 连接不同父节点的两个相邻节点
    connectTwoNode(root1->right, root2->left);
}

public: Node connect(Node root) { if(root == NULL) return root; connectTwoNode(root->left, root->right); return root; } };

复杂度分析:设二叉树共 N 个节点

- 时间复杂度 O(N):遍历每个节点一次
- 空间复杂度 O(log N):栈空间取决于递归深度,即二叉树的高度

执行结果:

执行结果:通过

执行用时:20 ms, 在所有 C++ 提交中击败了 54.53% 的用户 内存消耗:16.4 MB, 在所有 C++ 提交中击败了 77.31% 的用户 ```