LeetCode 116 Populating Next Right Pointers in Each Node

    
        标签：
        
            二叉树
        
            LeetCode
        
    发布于：2022-02-06 19:32:54
    编辑于：2022-02-06 19:59:07
    浏览量：750

概述

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

层序遍历

第一眼想到层序遍历，问题在于我们需要知道每层的结束，考虑到是完全二叉树，我们完全可以通过序号来判断其是否是每层的结尾。

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;
        vector<Node*> list;
        queue<Node*> q;
        q.push(root);
        while (!q.empty()) {
            auto c = q.front();
            q.pop();
            if (!c) continue;
            list.push_back(c);
            q.push(c->left);
            q.push(c->right);
        }
        int target = 0;
        int c = 0;
        for (int i = 0; i < list.size(); i++) {
            if (i == target) {
                c++;
                target += int(pow(2, c));
                continue;
            }
            list[i]->next = list[i+1];
        }
        return root;
    }
};

递归法

很明显，这道题即使递归也不能左右子树单独递归，亦即递归函数的参数不能只有一个节点，那要有几个？两个够了。

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;
        connectTwoNode(root->left, root->right);
        return root;
    }
    
    void connectTwoNode(Node* a, Node* b) {
        if (a == nullptr) return;
        // base case
        a->next = b;
        
        connectTwoNode(a->left, a->right);
        connectTwoNode(a->right, b->left);
        connectTwoNode(b->left, b->right);
    }
};

注意是完全二叉树，因此如果 a 和 b 必然同时为 nullptr。

Links: leetcode-116-populating-next-right-pointers-in-each-node