笔试时间：2023年3月23日 春招实习

第一题

题目：二叉树赋值

小红拿到了一个二叉树，二叉树共有n个节点。小红希望你将所有节点赋值为1到n的正整数，且没有两个节点的值相等。需要满足:奇数层的权值和与偶数层的权值和之差的绝对值不超过1。如果有多种赋值方案，请返回任意—种方案。如果无解，请返回空树。数据范围: 1<n ≤105。给定的二叉树节点初始权值默认为-1。

示例输入

示例一：

{-1,-1,-1}

示例二：

{-1,-1,#,-1,-1}

示例三：

{-1,-1,-1,#,-1,-1}

示例输出

示例一：

{3,1,2}

示例二：

{}

示例三：

{1,3,4,#,2,5}

参考题解

贪心。如果奇数层的节点数和偶数层的节点数大于等于2，必然无解。

分配策略为:较少数量的层[n,n-3....；较多数量的层[n-1,n-2....

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* fun(TreeNode* root) {
        vector<TreeNode*> odd, even;
        cnts(root, 1, odd, even);

        int n = odd.size() + even.size();
        if (abs(odd.size() - even.size()) >= 2) return nullptr;

        if (odd.size() < even.size()) swap(odd, even);
        int i = n - 3, j = n - 2;
        int sum1 = n, sum2 = n - 1;

        even[0]->val = n;
        odd[0]->val = n - 1;

        int index1 = 1, index2 = 1;
        for (int _ = 0; _ < n - 2; ++_) {
            if (sum1 <= sum2) {
                if (index1 >= even.size()) break;
                even[index1]->val = j;
                index1++;
                sum1 += j;
            } else {
                if (index2 >= odd.size()) break;
                sum2 += j;
                odd[index2]->val = j;
                index2++;
            }
            j--;
        }
        while (index1 < even.size()) {
            even[index1]->val = j;
            j--;
            index1++;
        }
        while (index2 < odd.size()) {
            odd[index2]->val = j;
            j--;
            index2++;
        }
        return root;
    }

    void cnts(TreeNode* node, int i, vector<TreeNode*>& odd, vector<TreeNode*>& even) {
        if (!node) return;
        if (i % 2 == 0) even.push_back(node);
        else odd.push_back(node);
        cnts(node->left, i + 1, odd, even);
        cnts(node->right, i + 1, odd, even);
    }
};

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class Solution {
    public TreeNode fun(TreeNode root) {
        List<TreeNode> odd = new ArrayList<>();
        List<TreeNode> even = new ArrayList<>();
        cnts(root, 1, odd, even);

        int n = odd.size() + even.size();
        if (Math.abs(odd.size() - even.size()) >= 2) return null;

        if (odd.size() < even.size()) {
            List<TreeNode> temp = odd;
            odd = even;
            even = temp;
        }
        int i = n - 3, j = n - 2;
        int sum1 = n, sum2 = n - 1;

        even.get(0).val = n;
        odd.get(0).val = n - 1;

        int index1 = 1, index2 = 1;
        for (int _ = 0; _ < n - 2; ++_) {
            if (sum1 <= sum2) {
                if (index1 >= even.size()) break;
                even.get(index1).val = j;
                index1++;
                sum1 += j;
            } else {
                if (index2 >= odd.size()) break;
                sum2 += j;
                odd.get(index2).val = j;
                index2++;
            }
            j--;
        }
        while (index1 < even.size()) {
            even.get(index1).val = j;
            j--;
            index1++;
        }
        while (index2 < odd.size()) {
            odd.get(index2).val = j;
            j--;
            index2++;
        }
        return root;
    }

    private void cnts(TreeNode node, int i, List<TreeNode> odd, List<TreeNode> even) {
        if (node == null) return;
        if (i % 2 == 0) even.add(node);
        else odd.add(node);
        cnts(node