Menu

Subscribe

LeetCode 116 [Populating Next Right Pointers in Each Node]

ShuyuFang on Leetcode

题目链接

题目描述

  • 给定一颗完美二叉树，要求将每个结点的next指针指向它右侧的结点，若它右侧没有结点，则指向NULL，处理过程只能使用常量复杂度的空间。

解题思路

  1. 对于任意两个在完美二叉树上左右相邻的结点，它们必定满足以下两个规则之一：
    1. 它们有同一个父结点，即任意一个结点的左右子结点必然是相邻的。
    2. 两个结点的父结点相邻，并且位于左侧的结点是它的父结点的右子结点，位于右侧的结点是它的父结点的左子结点。
  2. 既然确定了左右相邻的结点的特征，那么只需要从根结点开始遍历树的所有结点并对应处理即可，处理过程如下：
    1. 对于每个结点，若左子结点存在，那么右子结点也必然存在，则将左子结点的next指针指向右子结点。
    2. 对于每个结点，若它的左子结点也存在右子结点，那么它的右子结点也存在左子结点，则将它的左子结点的右子结点的next指针，指向它的右子结点的左子结点。
  3. 处理过程中，每个结点都被遍历了一次，因此时间复杂度是O(n)。

C++代码

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        if (root->next && root->right) root->right->next = root->next->left;
        if (root->left) {
            root->left->next = root->right;
            connect(root->left);
            connect(root->right);
        }
    }
};