题解 | 判断一棵满二叉树是否为二叉搜索树

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

class Solution {
public:
    bool check(vector<string>& nums, int index, long long min_val, long long max_val) {
        if (index >= nums.size()) {
            return true;
        }
        
        int val = stoi(nums[index]);
        if (val <= 0 || val >= 65536) {
            return false;
        }
        
        if (val <= min_val || val >= max_val) {
            return false;
        }
        
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < nums.size()) {
            return check(nums, left, min_val, val) && check(nums, right, val, max_val);
        }
        
        return true;
    }
};

int main() {
    string line;
    while (getline(cin, line)) {
        if (line == "None") {
            cout << "True" << endl;
            continue;
        }
        
        vector<string> nums;
        stringstream ss(line);
        string item;
        while (getline(ss, item, ',')) {
            nums.push_back(item);
        }
        
        Solution sol;
        try {
            cout << (sol.check(nums, 0, 0, 65536) ? "True" : "False") << endl;
        } catch (...) {
            cout << "False" << endl;
        }
    }
    return 0;
}

import java.util.*;

public class Main {
    public static boolean check(String[] nums, int index, long min_val, long max_val) {
        if (index >= nums.length) {
            return true;
        }
        
        try {
            long val = Long.parseLong(nums[index]);
            if (val <= 0 || val >= 65536) {
                return false;
            }
            
            if (val <= min_val || val >= max_val) {
                return false;
            }
            
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            
            if (left < nums.length) {
                return check(nums, left, min_val, val) && check(nums, right, val, max_val);
            }
            
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String line = sc.nextLine().trim();
            if (line.equals("None")) {
                System.out.println("True");
                continue;
            }
            
            String[] nums = line.split(",");
            System.out.println(check(nums, 0, 0L, 65536L) ? "True" : "False");
        }
    }
}

class Solution:
    def isValidBST(self, nums):
        # 空树情况
        if not nums or nums[0] == "None":
            return True
            
        # 转换输入为整数列表
        nums = [int(x) for x in nums]
        
        def check(index, min_val, max_val):
            if index >= len(nums):
                return True
                
            val = nums[index]
            if val <= 0 or val >= 65536:
                return False
                
            if val <= min_val or val >= max_val:
                return False
            
            # 检查左右子树
            left = 2 * index + 1
            right = 2 * index + 2
            
            # 满二叉树要么都有子节点，要么都没有
            if left < len(nums):
                if not check(left, min_val, val):
                    return False
                if not check(right, val, max_val):
                    return False
            
            return True
        
        return check(0, 0, 65536)

# 处理输入
while True:
    try:
        line = input().strip()
        if line == "None":
            print("True")
            continue
            
        nums = line.split(",")
        solution = Solution()
        print(str(solution.isValidBST(nums)))
    except:
        break