[实战演练]蜻蜓FM2014年校招笔试题目 – 规则二叉树

工程师浩然技术 2022年11月18日

0 收藏 933 点赞 3,192 浏览 839 个字

题目：某规则二叉树的定义是：对于树中任意两个叶结点A、B，他们与根结点的距离分别是d1和d2，|d1-d2|<=1。请写出函数 bool isRuledTree(Node *root)的代码实现。如果该二叉树为规则树，则返回true，否则返回false。

思路：其实就是比较所有叶结点的深度，最大值和最小值之间相差不超过1，则为规则树，可以遍历所有的结点，如果碰到叶结点，记录该叶结点的深度到数组或任意什么结构中，然后找到这些记录中的最大值和最小值，求差即可。在我的代码中，用一个栈结构存储叶结点的深度。代码实现如下：

typedef struct Node{
    int val;
    Node *right;
    Node *left;
} Node;stack<int> record;void isRuledTreeCore(Node *n, int depth){
    if(n->left == NULL && n->right == NULL){
        record.push(depth);
        return;
    }
    if(n->left != NULL)
        isRuledTreeCore(n->left,depth+);
    if(n->right != NULL)
        isRuledTreeCore(n->right,depth+);
    return;
}
bool isRuledTree(Node *root){
    if(root==NULL) return true;    isRuledTreeCore(root,);    int big=, small = INT_MAX;
    while(!record.empty()){
        int temp = record.top();
        if(temp>big) big = temp;
        if(temp<small) small = temp;
        record.pop();
    }
    if(big-small>=- && big-small<=)
        return true;
    return false;
}