PAT甲级-1115 Counting Nodes in a Binary Search Tree

题目

 题目大意

给定节点个数，以及每个节点的值，要求构造一棵二叉排序（搜索）树，并按照规定格式输出最后一层和倒数第二层的节点个数。

思路

二叉排序树的构造方法是递归，但思路类似于二分查找。逐个将n个节点插入到二叉排序树中，插入完成也就构造完成了。插入节点时，如果该节点值大于根节点，那么将它放入根节点的右子树中找，如果小于根节点，放入左子树，如此循环，直到找到一个空位置插入。

求最后一层的节点个数lowest和倒数第二层lower，可以先用dfs求出树的深度deep，顺便求lowest，再拿着deep用另一个dfs求lower。为了防止重复遍历，当递归层数num等于deep - 1时，就要return返回。

代码

#include <iostream>
using namespace std;

struct node{
    int data;
    node * lchild, * rchild;
};
int n, lower = 0, lowest = 0, deep = 0;

void buildTree(node * &root, int num){
    if (root == nullptr){
        root = new node();
        root->data = num;
        root->lchild = root->rchild = nullptr;
    }else{
        if (num > root->data){
            buildTree(root->rchild, num);
        }else{
            buildTree(root->lchild, num);
        }
    }
}  // 构建二叉排序树（二叉搜索树）

void dfs(node * root, int num){
    if (root->lchild == nullptr && root->rchild == nullptr){
        if (deep == num){
            lowest++;
        }else if (deep < num){
            deep = num;
            lowest = 1;
        }
    }else{
        if (root->lchild){
            dfs(root->lchild, num + 1);
        }
        if (root->rchild){
            dfs(root->rchild, num + 1);
        }
    }
}  // dfs得到总深度和最后一层的节点个数

void findLower(node * root, int num){
    if (num == deep - 1){
        lower++;
        return;  // 达到目标深度就return，以防重复遍历！！！
    }
    if (root->lchild){
        findLower(root->lchild, num + 1);
    }
    if (root->rchild){
        findLower(root->rchild, num + 1);
    }
}  // 已知总深度求目标深度的节点个数

int main(){
    cin >> n;
    node * root = nullptr;
    for (int i = 0; i < n; i++){
        int num;
        cin >> num;
        buildTree(root, num);
    }
    dfs(root, 0);
    findLower(root, 0);
    cout << lowest << " + " << lower << " = " << lowest + lower << endl;

    return 0;
}