程序员代码面试指南 3.8：找到二叉树符合条件的最大拓扑结构

1、思路

• 我们先考查root的孩子节点，根据孩子节点的值从root开始按照二叉搜索的方式移动，如果最后能移动到同一个孩子节点上，说明这个孩子节点可以作为这个拓扑的一部分，并继续考察这个孩子节点的孩子节点，一直延伸下去；

• 时间复杂度为 。

2、代码

#include <iostream>

using namespace std;

struct TreeNode                             //二叉树节点
{
    int val;
    TreeNode *left, *right;

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

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

    root->val = rootVal;

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

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

bool isBSTNode(TreeNode* root, TreeNode* node, int val)
{
    if (root == nullptr) return false;
    if (root == node) return true;

    //按照二叉搜索的方式移动
    return isBSTNode(root->val > val ? root->left : root->right, node, val);
}

int maxTopo(TreeNode* root, TreeNode* node)
{
    //第三个条件的作用是考察孩子节点是否可以作为这个拓扑序的一部分
    if (root != nullptr && node != nullptr && isBSTNode(root, node, node->val))
    {
        return maxTopo(root, node->left) + maxTopo(root, node->right) + 1;
    }

    return 0;
}

int bstTopoSize(TreeNode* root)             //计算二叉搜索树最大节点数
{
    if (root == nullptr) return 0;

    int maxSize = maxTopo(root, root);
    maxSize = max(maxSize, max(bstTopoSize(root->left), bstTopoSize(root->right)));

    return maxSize;
}

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

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

    int res = bstTopoSize(root);

    cout << res << endl;

    return 0;
}