程序员代码面试指南 3.15：判断一棵二叉树是否为搜索二叉树

1、思路

• 对于二叉搜索树的判断，可以在中序遍历时保存前一个节点的值，每次比较当前节点值与前一节点值，若前一节点值较大，则该二叉树不是二叉搜索树；

• 对于完全二叉树的判断，可以按照以下标准进行：

  1、层序遍历二叉树；

  2、若当前节点有右子节点却没有左子节点，则直接返回false；

  3、若当前节点并不是左右孩子都有，那么之后的节点必须都为叶子结点，否则返回false；

  4、遍历过程中若不返回false，则遍历结束后返回true。

2、代码

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left, *right;

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

//建树
void createTree(TreeNode *root)
{
    int rootVal, leftVal, rightVal;
    cin >> rootVal >> leftVal >> rightVal;

    root->val = rootVal;

    if (leftVal != 0)
    {
        root->left = new TreeNode(leftVal);
        createTree(root->left);
    }

    if (rightVal != 0)
    {
        root->right = new TreeNode(rightVal);
        createTree(root->right);
    }
}

//判断二叉搜索树（二叉树中序遍历的迭代版）
bool isBST(TreeNode *root)
{
    if (root == nullptr) return true;

    stack<TreeNode*> stk;
    TreeNode *p = root, *pre = nullptr;

    while (p != nullptr || !stk.empty())
    {
        if (p != nullptr)
        {
            stk.push(p);
            p = p->left;
        }
        else
        {
            p = stk.top();
            stk.pop();

            if (pre != nullptr && pre->val >= p->val)
            {
                return false;
            }

            pre = p;            //更新前一节点的值
            p = p->right;
        }
    }

    return true;
}

//判断完全二叉树（二叉树的层序遍历）
bool isCBT(TreeNode *root)
{
    if (root == nullptr) return true;

    queue<TreeNode*> q;
    q.push(root);

    TreeNode *left, *right;
    bool isLeaf = false;

    while (!q.empty())
    {
        TreeNode *node = q.front();
        q.pop();

        left = node->left;
        right = node->right;

        //情况 2 和 情况 3
        if ((isLeaf && (left != nullptr || right != nullptr)) || 
            (left == nullptr && right != nullptr))
        {
            return false;
        }

        if (left != nullptr)
        {
            q.push(left);
        }

        if (right != nullptr)
        {
            q.push(right);
        }
        else
        {
            //若没有右子树，则该节点之后的所有节点均为叶子节点
            isLeaf = true;
        }
    }

    return true;
}

int main()
{
    int n, rootVal;
    cin >> n >> rootVal;

    TreeNode *root = new TreeNode(rootVal);
    createTree(root);

    if (isBST(root))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    if (isCBT(root))
    {
        cout << "true" << endl;
    }
    else
    {
        cout << "false" << endl;
    }

    return 0;
}