LeetCode 116 Populating Next Right Pointers in Each Node

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

概述

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。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/