CD81.【C++ Dev】判断二叉搜索树是否是红黑树

https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/

给定一个整数数组，它表示BST(即 二叉搜索树 )的先序遍历 ，构造树并返回其根。

保证对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

示例 1：
输入：preorder = [8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]
示例 2:
输入: preorder = [1,3]
输出: [1,null,3]
提示：

1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
preorder 中的值 互不相同

分析

观察题目给的preorder = [8,5,1,7,10,12]的规律:

8→5→1是递减的,1→7是递增的,7→10→12是递增的,

1.如果是递减的顺序,就一直插入到末端节点的左子树

2.如果是递增的顺序,需要使用遍历过的路径,先向上查找合适的节点,再插入到合适的节点的右子树处

存储遍历过的路径可以用栈存储节点的地址,这里用节点存储的数字来代替地址

现在插入7:

栈顶的1小于7,弹出; 栈顶的5小于7,弹出; 栈顶的8大于7,第一次出现大于,停止栈操作,需要将7插入到5的右子树→保留之前的栈顶元素,这样就不会丢失需要被插入的节点的地址了

再将7入栈,继续插入剩下的节点:

现在插入10:

栈顶的7小于10,弹出; 栈顶的8小于10,弹出; 发现栈为空,之前的栈顶元素为8,那就插入10到8的右子树

插入12这里省略,操作类似

*注: 其实这是单调栈(满足从栈底到栈顶是严格递减)的算法,其实不用记忆,可以手动推出

代码

class Solution 
{
public:
    TreeNode* create_node(int val)
    {
        TreeNode* newnode = new TreeNode(val);
        return newnode;
    }
    TreeNode* bstFromPreorder(const vector<int>& preorder)
    {
        TreeNode* root= nullptr;
        for (auto num : preorder)
        {
            if (root == nullptr)
            {
                root = create_node(num);
                st.push(root);
            }
            else
            {
                if (st.top()->val > num)
                {
                    st.top()->left = create_node(num);
                    st.push(st.top()->left);
                }
                else//st.top()->val<num
                {
                    TreeNode* prev_top;//暂存之前的栈顶元素
                    //条件顺序不能交换,因为短路运算
                    while ( st.size()>0&&st.top()->val < num)
                    {
                        prev_top = st.top();
                        st.pop();
                    }
                    //st.top()->val>num
                    prev_top->right = create_node(num);
                    st.push(prev_top->right);
                }
            }
        }
        return root;
    }
    stack<TreeNode*> st;
};

分析时间复杂度

从栈的视角来看,每个节点最多入栈一次、出栈一次,虽然内层有while循环,但所有节点的总弹出次数≤n,因此平均复杂度是 $O(N)$

提交结果

3.PAT(Advanced Level) 1135 Is It A Red-Black Tree

https://pintia.cn/problem-sets/994805342720868352/exam/problems/type/7?page=1&problemSetProblemId=994805346063728640

There is a kind of balanced binary search tree named red-black tree in the data structure. It has the following 5 properties:

(1) Every node is either red or black.
(2) The root is black.
(3) Every leaf (NULL) is black.
(4) If a node is red, then both its children are black.
(5) For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

For example, the tree in Figure 1 is a red-black tree, while the ones in Figure 2 and 3 are not.

Figure 1 Figure 2 Figure 3

For each given binary search tree, you are supposed to tell if it is a legal red-black tree.

Input Specification:

Each input file contains several test cases. The first line gives a positive integer K (≤30) which is the total number of cases. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the preorder traversal sequence of the tree. While all the keys in a tree are positive integers, we use negative signs to represent red nodes. All the numbers in a line are separated by a space. The sample input cases correspond to the trees shown in Figure 1, 2 and 3.

Output Specification:

For each test case, print in a line "Yes" if the given tree is a red-black tree, or "No" if not.

Sample Input:
3
9
7 -2 1 5 -4 -11 8 14 -15
9
11 -2 1 -7 5 -4 8 14 -15
8
10 -7 5 -6 8 15 -11 17
Sample Output:
Yes
No
No


Figure 1	Figure 2	Figure 3

分析

提炼出关键条件

1.给的是二叉搜索树前序遍历序列

2.注意格式:

第一行给出测试用例的总数

对于每个测试用例,第一行给出二叉树中的节点总数,第二行给出该树的前序遍历序列

2.前序遍历序列中,所有键均为正整数,我们用负号表示红色结点,那么正数表示黑色结点

代码框架

显然分为两步: 1.用动态分配空间的方式构造二叉搜索树 2.判断二叉搜索树是否是红黑树

代码

构造二叉搜索树

稍微修改下LeetCode代码的bstFromPreorder函数

enum Color
{
    RED,
    BLACK
};
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
    Color _col;
    TreeNode(int x) :left(nullptr), right(nullptr),parent(nullptr)
    {
        if (x < 0)
        {
            val = -x;
            _col = RED;
        }
        else
        {
            val = x;
            _col = BLACK;
        }
    }
};

需要修改LeetCode的bstFromPreorder,为parent赋值

判断二叉搜索树是否是红黑树

回忆红黑树的4个性质:

1.前提是二叉搜索树
2.根结点以及叶子结点是黑色的

★注意:这里的叶子结点不是常规意义上的叶子结点,而是指空结点

3.红色结点的左右孩子必须是黑色的,换句话说,任意一条路径中,不会存在连续的红色结点
4.任一结点到叶子结点的路径上,黑色结点的数量相同

注意:

1.不需要检查"最长路径不超过最短路径的2倍",满足了上面这4个性质就满足了最长路径和最短路径之间的关系

2.性质1已经按前序遍历构造过二叉搜索树了,不需要检查

检查2、3和4即可:

性质2: 先检查根结点

bool is_rbtree()
{
    //性质1: 根结点是黑色的
    if (root->_col == RED)
        return false;
    //用子函数递归检查
    return _is_rbtree(root);
}

叶子结点是NIL结点,为nullptr可以不检查,不影响性质3的验证

性质3: 检查是否有连续的红节点,遍历整棵树(边遍历边检查)即可

4种遍历方法参见:

106.【C语言】数据结构之二叉树的三种递归遍历方式

109.【C语言】数据结构之二叉树层序遍历

性质4:遍历整棵树检查

先挑一个路径算黑色结点的数量,例如一直向左统计黑色结点的数量,实现起来比较简单

//先给一个基准值,方便之后比较
int black_node_cnt = 0;
while (cur)
{
    if (cur->_col == BLACK)
        black_node_cnt++;
    cur = cur->left;
}

之后检查左右子树:

//bool _is_rbtree(TreeNode* root)内部
return check(root,black_node_cnt);

递归检查:

走到NIL结点才能求出黑色结点的数量

bool check(TreeNode* _root,int blacknum,const int& black_node_cnt)
{
    if (_root == nullptr)
    {
        if (blacknum != black_node_cnt)
            return false;
        return true;
    }
    //出现连续的红节点
    if (_root->_col == RED && _root->parent && _root->parent->_col == RED)
        return false;
    if (_root->_col == BLACK)
        blacknum++;
    //递归检查左右子树
    return check(_root->left, blacknum, black_node_cnt) && check(_root->right, blacknum,black_node_cnt);
}

★blacknum和black_node_cnt的类型问题

black_node_cnt是求出来的基准值,在调用check时不会变化,可以引用+const,即const int& black_node_cnt

blacknum不能加引用,因为每条路径需要算各自的黑色结点的数量(即每个check函数的栈帧里面都有一个blacknum),不能影响到其他路径的blacknum

注: 如果blacknum加了引用,算出来的结果是整棵树的黑色结点的数量

main函数代码

使用循环来按组读取即可,竞赛中可以使用解除同步sync_with_stdio和取消绑定tie来提高cin/cout的性能,写在main函数的前面

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int group, cnt, num;
    cin >> group;
    while (group--)
    {
        cin >> cnt;
        binary_search_tree bst;
        while (cnt--)
        {
            cin >> num;
            bst.bstFromPreorder(num);
        }
        if (bst.is_rbtree())
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

完整代码

#include <vector>
#include <stack>
#include <iostream>
using namespace std;
enum Color
{
    RED,
    BLACK
};
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
    Color _col;
    TreeNode(int x) :left(nullptr), right(nullptr),parent(nullptr)
    {
        if (x < 0)
        {
            val = -x;
            _col = RED;
        }
        else
        {
            val = x;
            _col = BLACK;
        }
    }
};

class binary_search_tree
{
public:
    TreeNode* create_node(int val)
    {
        TreeNode* newnode = new TreeNode(val);
        return newnode;
    }
    void bstFromPreorder(int num)
    {
        if (root == nullptr)
        {
            root = create_node(num);
            st.push(root);
        }
        else
        {
            int _num = num;
            if (num < 0)
                _num = -num;
            if (st.top()->val > _num)
            {
                st.top()->left = create_node(num);
                st.top()->left->parent = st.top();
                st.push(st.top()->left);
            }
            else//st.top()->val<_num
            {
                TreeNode* prev_top=nullptr;//暂存之前的栈顶元素
                //条件顺序不能交换,因为短路运算
                while (st.size() > 0 && st.top()->val < _num)
                {
                    prev_top = st.top();
                    st.pop();
                }
                //st.top()->val>num
                prev_top->right = create_node(num);
                prev_top->right->parent = prev_top;
                st.push(prev_top->right);
            }
        }
    }
    bool is_rbtree()
    {
        //性质1: 根结点是黑色的
        if (root->_col == RED)
            return false;
        return _is_rbtree(root);
    }
    bool check(TreeNode* _root,int blacknum,const int& black_node_cnt)
    {
        if (_root == nullptr)
        {
            if (blacknum != black_node_cnt)
                return false;
            return true;
        }
        //出现连续的红节点
        if (_root->_col == RED && _root->parent && _root->parent->_col == RED)
            return false;
        if (_root->_col == BLACK)
            blacknum++;
        //递归检查左右子树
        return check(_root->left, blacknum, black_node_cnt) && check(_root->right, blacknum,black_node_cnt);
    }
    bool _is_rbtree(TreeNode* root)
    {
        if (root == nullptr)
            return true;
        //先给一个基准值,方便之后比较
        TreeNode* cur = root;
        int black_node_cnt = 0;
        while (cur)
        {
            if (cur->_col == BLACK)
                black_node_cnt++;
            cur = cur->left;
        }
        return check(root,0,black_node_cnt);
    }
    stack<TreeNode*> st;
    TreeNode* root = nullptr;
};


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int group, cnt, num;
    cin >> group;
    while (group--)
    {
        cin >> cnt;
        binary_search_tree bst;
        while (cnt--)
        {
            cin >> num;
            bst.bstFromPreorder(num);
        }
        if (bst.is_rbtree())
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}