题目详情

红黑树是自平衡二叉查找树，具有一下性质：红黑树的根节点是黑色；红节点的子节点是黑的；从任何一个节点A出发，到后代叶子节点的所有路径拥有相同的黑节点数。

要求判断所给的前序遍历序列是否是红黑树。

我的版本

首先需要根据红黑树的性质还原红黑树，我用的是递归；

创建好红黑树之后，需要判断(1)相邻节点是否全为红节点、(2)路径黑节点数是否一致。对于(1)，直接判断即可；对于(2)，类似于动态规划的思想，从叶子节点判断起，使用递归实现状态转移。

import java.util.*;
public class Main {
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        while (k-- > 0) {
            n = sc.nextInt();
            int[] pre = new int[n];
            for (int i = 0; i < n; i ++) {
                pre[i] = sc.nextInt();
            }
            if (pre[0] < 0) {
                System.out.println("No");
            } else {
                node root = create(pre, 0, n);
                int bool = judge(root);
                if (bool == -1) {
                    System.out.println("No");
                } else {
                    System.out.println("Yes");
                }
            }
        }
    }
    static int judge(node root) {
        int l = 0, r = 0;
        if (root.left != null) {
            if (root.value < 0 && root.left.value < 0) return -1;   // 相邻节点不能全为红
            l = judge(root.left);
        }
        if (root.right != null) {
            if (root.value < 0 && root.right.value < 0) return -1;  // 相邻节点不能全为红
            r = judge(root.right);
        }
        if (l >= 0 && l == r) {  
            if (root.value > 0) return l + 1;
            else return l;
        } 
        return -1;
    }
    static node create(int[] pre, int begin, int end) {
        if (begin == end) 
            return null;
        node root = new node(pre[begin]);
        int i = begin+1;
        for (i = begin+1; i < end; i ++) {
            if (Math.abs(pre[i]) > Math.abs(pre[begin])) break;
        }
        root.left = create(pre, begin+1, i);
        root.right = create(pre, i, end);
        return root;
    }
    static class node {
        int value;
        node left;
        node right;
        public node(int val) {
            this.value = val;
        }
    }
}