二叉树笔试题

题目：输入两棵二叉树A和B，判断树B是不是A的子结构

bool IsChildTree(Node * father, Node * son)
{
    if(father == NULL && son == NULL)
        return true;

    if(father == NULL && son != NULL)
        return false;

    if(father != NULL && son == NULL)
        return true;

    //如果当前结点相同，判断左右子树是否子结构
    if(father->data == son->data )
    {
         return IsChildTree(father->left, son->left) && IsChildTree(father->right, son->right);
    }

    //判断son子树是否是左子树的子结构
    if(IsChildTree(father->left, son))
        return true;

    //判断son子树是否是右子树的子结构
    if(IsChildTree(father->right, son))
        return true;

    return false;
}

题目：寻找最近公共祖先LCA（Lowest Common Ancestor）

Node* getLCA(Node* root, Node* x, Node* y)
{
    if(root == NULL) return NULL;

    if(x == root || y == root)
        return root;

    Node* pleft = getLCA(root->left, x, y);
    Node* pright = getLCA(root->right, x, y);

    if(pleft == NULL)
        return pright;
    else if(pright == NULL)
        return pleft;

    else return root;
}

分别得到根节点root到结点x的路径和到结点y的路径，由于这个路径是从跟结点开始的，最低的共同父结点就是路径中的最后一个共同结点，即是LCA。

//得到根节点pHead到pNode的路径
bool GetNodePath(Node* pHead, Node* pNode, std::list<Node*>& path)
{
    if(pHead == pNode)
        return true;

    path.push_back(pHead);

    bool found = false;

    if(pHead->left != NULL)
        found = GetNodePath(pHead->left, pNode, path);

    if(!found && pHead->right)
        found = GetNodePath(pHead->right, pNode, path);

    if(!found)
        path.pop_back();

    return found;
}

// 从两个列表path1和path2中得到最后一个共同的结点
TreeNode* LastCommonNode(const std::list<TreeNode*>& path1, const std::list<TreeNode*>& path2)
{
    std::list<TreeNode*>::const_iterator iterator1 = path1.begin();
    std::list<TreeNode*>::const_iterator iterator2 = path2.begin();
    TreeNode* pLast = NULL;
    while(iterator1 != path1.end() && iterator2 != path2.end())
    {
        if(*iterator1 == *iterator2)
            pLast = *iterator1;
        iterator1++;
        iterator2++;
    }
    return pLast;
}

题目：寻找二叉搜索树（BST）的最低公共祖先（LCA）

利用BST的性质：从根结点开始搜索，当第一次遇到当前结点的值介于两个给定的结点值之间时，这个当前结点就是要找的LCA。

Node* FindLCA(Node* root,int x, int y)
{
    Node * t = root;
    while(1)
    {
        if(t->data > x && t->data > y)
            t = t->left;
        else if(t->data < x && t->data < y)
            t = t->right;
        else return t;
    }
}

题目：寻找BST中序遍历序列中第k个元素

void findK(Node* p, int& k)
{
    if(!p || k < 0) return;
    findK(p->left, k);
    -- k;
    if(k == 0)
    {
        print p->data;
        return;
    }
    findK(p->right, k);
}

题目：求二叉树中相距最远的两个节点之间的距离

求两节点的最远距离，实际就是求二叉树的直径。本问题可以转化为求“二叉树每个节点的左右子树高度和的最大值”。

int TreeHeight(Node* root, int& max_distance)
{
    if(root == NULL)
    {
        max_distance = 0;
        return 0;
    }

    int left_height,right_height;

    if(root->left)
        left_height = TreeHeight(root->left,max_distance)+1;
    else
        left_height = 0;

    if(root->right)
        right_height = TreeHeight(root->right,max_distance)+1;
    else
        right_height = 0;

    int distance = left_height + right_height;
    if (max_distance < distance) max_distance = distance;

    return (left_height > right_height ? left_height : right_height);
}

int TreeDiameter(Node* root)
{
    int max_distance = 0;
    if(root) TreeHeight(root, max_distance);
    return max_distance;
}

题目：求二叉树中节点的最大距离：如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，定义“距离”为两节点之间边的个数。（此题就是求二叉树中相距最远的两个节点之间的距离，代码来自《编程之美》）

//结点的定义
typedef struct Node
{
    Node * left;
    Node * right;
    int maxLeft;
    int maxRight;
    char chValue;
}Node,*pNode;

//最大距离
int maxLen = 0;

//寻找二叉树中节点的最大距离
void findMaxLength(Node* root)
{
    if(root == NULL) return;

    //如果左子树为空，则该节点左边最长距离为0
    if(root->left == NULL)     root->maxLeft = 0;

    //如果右子树为空，则该节点右边最长距离为0
    if(root->right == NULL)    root->maxRight = 0;

    //如果左子树不为空，递归寻找左边最长距离
    if(root->left != NULL)     findMaxLength(root->left);

    //如果右子树不为空，递归寻找右边最长距离
    if(root->right != NULL)    findMaxLength(root->right);

    //计算左子树最长节点距离
    if(root->left != NULL)
    {
        int tempMax = 0;
        if(root->left->maxLeft > root->left->maxRight)
            tempMax = root->left->maxLeft;
        else tempMax = root->left->maxRight;
        root->maxLeft = tempMax+1;
    }

    //计算右子树最长节点距离
    if(root->right != NULL)
    {
        int tempMax = 0;
        if(root->right->maxLeft > root->right->maxRight)
            tempMax = root->right->maxLeft;
        else tempMax = root->right->maxRight;
        root->maxRight = tempMax+1;
    }

    //更新最长距离
    if(root->maxLeft+root->maxRight > maxLen)
        maxLen = root->maxLeft+root->maxRight;
}

题目：重建二叉树，通过先序遍历和中序遍历的序列可以唯一确定一棵二叉树（通过中序和后序遍历的序列也可以唯一确定一棵二叉树，但是不能通过先序和后序遍历序列唯一确定二叉树）

//通过先序遍历和中序遍历的序列重建二叉树
void ReBuild(char* pPreOrder,char* pInOrder,int nTreeLen,Node** pRoot)
{
    //检查边界条件
    if(pPreOrder == NULL || pInOrder == NULL)
        return;

    //获得前序遍历的第一个节点
    Node* temp = new Node;
    temp->data = *pPreOrder;
    temp->left = NULL;
    temp->right = NULL;

    //如果节点为空，把当前节点复制到根节点
    if(*pRoot == NULL) *pRoot = temp;

    //如果当前树长为1，那么已经是最后一个节点
    if(nTreeLen == 1) return;

    //寻找子树长度
    char* pOrgInOrder = pInOrder;
    char* pLeftEnd = pInOrder;
    int nTempLen = 0;

    //找到左子树的结尾
    while(*pPreOrder != *pLeftEnd)
    {
        if(pPreOrder == NULL || pLeftEnd == NULL)
            return;
        //记录临时长度，以免溢出
        nTempLen++;
        if(nTempLen > nTreeLen) break;
        pLeftEnd++;
    }

    //寻找左子树长度
    int nLeftLen = (int)(pLeftEnd-pOrgInOrder);

    //寻找右子树长度
    int nRightLen = nTreeLen-nLeftLen-1;

    //重建左子树
    if(nLeftLen > 0)
        ReBuild(pPreOrder+1,pInOrder,nLeftLen,&((*pRoot)->left));

    //重建右子树
    if(nRightLen > 0)
        ReBuild(pPreOrder+nLeftLen+1,pInOrder+nLeftLen+1,nRightLen,&((*pRoot)->right));
}

题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。

例如输入整数22和如下二元树

                                             10
                                            /  \
                                           5   12
                                         /   \   
                                       4      7 

则打印出两条路径：10, 12和10, 5, 7。

分析：这是百度的一道笔试题，考查对树这种基本数据结构以及递归函数的理解。 当访问到某一结点时，把该结点添加到路径上，并累加当前结点的值。如果当前结点为叶结点并且当前路径的和刚好等于输入的整数，则当前的路径符合要求，把它打印出来。如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是根结点到父结点的路径。我们不难看出保存路径的数据结构实际上是一个栈结构，因为路径要与递归调用状态一致，而递归调用本质就是一个压栈和出栈的过程。

#include <iostream>
#include <vector>
using namespace std;

struct Node
{
    int value;
    Node* left;
    Node* right;
    Node(){ left = NULL; right = NULL; }
    Node(int v){ value = v; left = NULL; right = NULL; }
};

void findpath(Node* root,vector<int>& nodes,int sum)
{
    if(root == NULL) return;
    nodes.push_back(root->value);
    if(root->left == NULL && root->right == NULL)
    {
        if(root->value == sum)
        {
            for(int i=0; i<nodes.size(); i++)
                cout<<nodes[i]<<" ";
            cout<<endl;
        }
    }
    else
    {
        if(root->left != NULL)
        {
            findpath(root->left,nodes,sum-root->value);
        }
        if(root->right != NULL)
        {
            findpath(root->right,nodes,sum-root->value);
        }
    }
    nodes.pop_back();
}

int main()
{
    Node *tmp ;
    Node* root = new Node(10);
    tmp = new Node(5);
    root->left = tmp ;
    tmp = new Node(12);
    root->right = tmp;
    tmp = new Node(4);
    root->left->left = tmp;
    tmp = new Node(7);
    root->left->right = tmp;
    vector<int> v;
    findpath(root,v,22);
    return 0;
}

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

         8
       /   \
      6     10
     / \     /  \
   5   7  9    11

因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。

分析：在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于根节点开始到根结点前面的一个元素为止，所有元素都应该大于根结点，因为这部分元素对应的是树的右子树。根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。

bool verifySquenceOfBST(int squence[], int length)
{
    if(squence == NULL || length <= 0)
        return false;

    // root of a BST is at the end of post order traversal squence
    int root = squence[length - 1];

    // the nodes in left sub-tree are less than the root
    int i = 0;
    for(; i < length - 1; ++ i)
    {
        if(squence[i] > root)
            break;
    }

    // the nodes in the right sub-tree are greater than the root
    int j = i;
    for(; j < length - 1; ++ j)
    {
        if(squence[j] < root)
            return false;
    }

    // verify whether the left sub-tree is a BST
    bool left = true;
    if(i > 0)
        left = verifySquenceOfBST(squence, i);

    // verify whether the right sub-tree is a BST
    bool right = true;
    if(i < length - 1)
        right = verifySquenceOfBST(squence + i, length - i - 1);

    return (left && right);
}

题目：怎样编写一个程序，把一个有序整数数组放到二叉搜索树中？

分析：本题考察二叉搜索树的建树方法。关于树的算法设计一定要联想到递归，因为树本身就是递归的定义。

Node* array_to_tree(int array[], int start, int end)
{
    if (start > end) return NULL;
    int m = start + (end-start)/2;
    Node* root = new Node(array[m]);
    root->left = array_to_tree(array, start, m-1);
    root->right = array_to_tree(array, m+1, end);
    return root;
}

Node* array2Tree(int array[], int n)
{
    return array_to_tree(array,0,n-1);
}

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。比如将二元查找树

                                            10
                                          /    \
                                        6       14
                                      /  \     /　 \
                                 　4     8  12 　16

转换成双向链表 4=6=8=10=12=14=16。

　　分析：本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也不例外。下面我们用两种不同的递归思路来分析。

　　思路一：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树，将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最后链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调整所有结点。

　　思路二：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

    //定义二元查找树结点的数据结构如下：
   struct BSTreeNode // a node in the binary search tree
    {
        int        m_nValue; // value of node
        BSTreeNode *m_pLeft; // left child of node
        BSTreeNode *m_pRight; // right child of node
    };

思路一对应的代码：

// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
//        asRight - whether pNode is the right child of its parent
// Output: if asRight is true, return the least node in the sub-tree
//         else return the greatest node in the sub-tree
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
{
    if(!pNode) return NULL;

    BSTreeNode *pLeft = NULL;
    BSTreeNode *pRight = NULL;

    // Convert the left sub-tree
    if(pNode->m_pLeft)
        pLeft = ConvertNode(pNode->m_pLeft, false);

    // Connect the greatest node in the left sub-tree to the current node
    if(pLeft)
    {
        pLeft->m_pRight = pNode; //m_pRight pointer works as the "next" pointer
        pNode->m_pLeft = pLeft;  //m_pLeft pointer works as the "previous" pointer
    }

    // Convert the right sub-tree
    if(pNode->m_pRight)
        pRight = ConvertNode(pNode->m_pRight, true);

    // Connect the least node in the right sub-tree to the current node
    if(pRight)
    {
        pNode->m_pRight = pRight;
        pRight->m_pLeft = pNode;
    }

    BSTreeNode *pTemp = pNode;

    // If the current node is the right child of its parent,
    // return the least node in the tree whose root is the current node
    if(asRight)
    {
        while(pTemp->m_pLeft)
            pTemp = pTemp->m_pLeft;
    }
    // If the current node is the left child of its parent,
    // return the greatest node in the tree whose root is the current node
    else
    {
        while(pTemp->m_pRight)
            pTemp = pTemp->m_pRight;
    }

    return pTemp;
}

// Covert a binary search tree into a sorted double-linked list
// Input: the head of tree
// Output: the head of sorted double-linked list
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
    // As we want to return the head of the sorted double-linked list,
    // we set the second parameter to be true
    return ConvertNode(pHeadOfTree, true);
}

思路二对应的代码：

// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
//        pLastNodeInList - the tail of the double-linked list
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
    if(pNode == NULL)
        return;

    BSTreeNode *pCurrent = pNode;

    // Convert the left sub-tree
    if (pCurrent->m_pLeft != NULL)
        ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

    // Put the current node into the double-linked list
    pCurrent->m_pLeft = pLastNodeInList;
    if(pLastNodeInList != NULL)
        pLastNodeInList->m_pRight = pCurrent;

    pLastNodeInList = pCurrent;

    // Convert the right sub-tree
    if (pCurrent->m_pRight != NULL)
        ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

// Covert a binary search tree into a sorted double-linked list
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
    BSTreeNode *pLastNodeInList = NULL;
    ConvertNode(pHeadOfTree, pLastNodeInList);

    // Get the head of the double-linked list
    // m_pLeft pointer works as the "previous" pointer in the double-linked list
    BSTreeNode *pHeadOfList = pLastNodeInList;
    while(pHeadOfList && pHeadOfList->m_pLeft)
        pHeadOfList = pHeadOfList->m_pLeft;

    return pHeadOfList;
}

参考：
《编程之美》
《剑指Offer》http://zhedahht.blog.163.com

作者：阿凡卢

出处：http://www.cnblogs.com/luxiaoxun/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

http://www.cnblogs.com/luxiaoxun/archive/2012/11/11/2765116.html

时间： 2024-08-02 13:52:35

二叉树笔试题的相关文章

经典算法(9) 从归并排序到数列的逆序数对（微软笔试题）

首先来看看原题 微软2010年笔试题 在一个排列中,如果一对数的前后位置与大小顺序相反 ,即前面的数大于后面的数,那么它们就称为一个逆序数对.一个排列中逆序的总数就称为这个排列的逆序 数.如{2,4,3,1}中,2和1,4和3,4和1,3和1是逆序数对,因此整个数组的逆序数对个数为4,现在给定 一数组,要求统计出该数组的逆序数对个数. 计算数列的逆序数对个数最简单的方便就最从前向后依 次统计每个数字与它后面的数字是否能组成逆序数对.代码如下: #include <stdio.h> int ma

网页转换-请问设计了一套笔试题（word2007版），如何转换成网页格式并具备倒计时功能？

问题描述 请问设计了一套笔试题(word2007版),如何转换成网页格式并具备倒计时功能? 我设计了一套人格测试题,都是选择题,用的是word07版,希望将答题时间限定在15分钟内,在候选人点击进去时便开始倒计时,咨询了一位IT朋友,她说要转换成网页格式并下一个插件,请教各位大神,应该如何做才能实现计划功能?谢谢! 解决方案 http://www.officezu.com/a/word/6203.html 解决方案二: 网页的话,js有很多第三方计时库

阿里巴巴一道智力题笔试题

问题描述 阿里巴巴一道智力题笔试题 有三张牌A,B,C,其中一张是King.如果你押中了King,那么就获胜,否则就输.现在你选择了押其中的一张牌1,电脑帮你排除了另外两张牌中的一张2,那么你是否重新选择押3,从而更容易获胜? http://www.manong1024.com/q/403 解决方案 google 三扇门问题真怀疑这是不是阿里的题,感觉很低级很low,像庙会灯谜上的题. 解决方案二: 假设挑选A其为king的概率p=1/3剩下的BC中为king的概率p=2/3.假设主持人又给你排

C++笔试题汇总（45题）

本文转自:<程序员必看c++笔试题汇总>,经过整理正文如下: 本文通过对程序员笔试过程的总结,对程序员c++笔试题进行了汇总.希望能与大家共同分享.下面是一些常见题型: 1.求下面函数的返回值(微软) { int countx = 0; while(x) { countx ++; x = x&(x-1); } return countx; } 假定x = 9999. 答案:8 思路:将x转化为2进制,看含有的1的个数. 2. 什么是"引用"?申明和使用"引

程序员必看 c++笔试题汇总

本文通过对程序员笔试过程的总结,对程序员c++笔试题进行了汇总.希望能与大家共同分享.下面是一些常见题型: 1.求下面函数的返回值(微软) {   int countx = 0;   while(x)   {   countx ++;   x = x&(x-1);   }   return countx;   }  假定x = 9999. 答案:8 思路:将x转化为2进制,看含有的1的个数. 2. 什么是"引用"?申明和使用"引用"要注意哪些问题? 答:引用

代码分析-一道Java笔试题，求解答（关于类的加载与初始化）

问题描述 一道Java笔试题,求解答(关于类的加载与初始化) 自己查了一些资料,还是看不懂这个程序的输出结果,求各位详细解释初始化和执行过程,谢! public class Alibaba { public static int k = 0; public static Alibaba t1 = new Alibaba("t1"); public static Alibaba t2 = new Alibaba("t2"); public static int i =

java算法题，公司的笔试题

问题描述 java算法题,公司的笔试题 suppose you have N cakes, N is an interger>0 // at each time, you can either eat 1 cake, or 2 cakes or 3 cakes // PROBLEM: How many ways can you eat all N cakes // for example, N = 4, (1,2,1) and (1,1,2) are considered to be diffe

相对路径 绝对路径-有一道去哪网校园招聘的笔试题大家帮忙看一下，是关于相对路径转绝对路径的

问题描述 有一道去哪网校园招聘的笔试题大家帮忙看一下,是关于相对路径转绝对路径的 1.写一个函数,转换相对路径为绝对路径,比如:/home/abs/../temp/new/../,输出路径为:/home/temp

要出发公司笔试题

前言 招聘高峰期来了,大家都非常积极地准备着跳槽,那么去一家公司面试就会有一堆新鲜的问题,可能不会,也可能会,但是了解不够深.本篇文章为群里的小伙伴们去要出发公司的笔试题,由笔者整理并提供笔者个人参考答案.注意,仅供参考,不代表绝对正确. 参考答案不唯一,大家可以根据自己的理解回答,没有必要跟笔者的一样.参考笔者的答案,也许给你带来灵感! 题目照 1.编程规范问题 这题看不清楚,不过可以看得出来是编程规范问题.所以呢,笔者也就没有办法说明哪些不合理了.不过笔者曾经为公司的出过一个编程规范文档,后