您的位置: 首页  >  IT文章  >  面试题汇总之二叉树（连载中）

面试题汇总之二叉树（连载中）

分类: IT文章 • 2023-11-22 23:29:07
面试题集锦之二叉树（连载中）

写在前面

    最近开始关注找工作，所以四处搜索各种算法题来练手，希望有志同道合的朋友不吝赐教！
  

基础知识

面试题汇总之二叉树（连载中）


面试题集锦

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

  10
  / /
 6 14
 / / / /
4 8 12 16   
 转换成双向链表
4=6=8=10=12=14=16。   
  首先我们定义的二元查找树 节点的数据结构如下：
 struct BSTreeNode
{
  int m_nValue; // value of node
  BSTreeNode *m_pLeft; // left child of node
  BSTreeNode *m_pRight; // right child of node
};                              
遍历BS树中的最小节点(即循环搜索左子树)，返回指向它的指针和它的父节点指针，从树中删除该节点

//BS tree 转换成排序双向链表，不能创建新的节点
//时间: 一小时
//错误: 小于三次
//错误1:节点的定义中元素不能没有struct
//错误2:需要修改一个指针参数，那么需要参数类型为**
#include <stdio.h>
#include <string.h>

struct BSTreeNode
{
	int m_nValue; 					// value of node
	struct BSTreeNode *m_pLeft; 	// left child of node	//错误1
	struct BSTreeNode *m_pRight; 	// right child of node
}; 
struct BSTreeNode *cur=NULL;		//指向最后选出的节点

void getMin(struct BSTreeNode * root, struct BSTreeNode ** min
	       ,struct BSTreeNode ** minPar)
{
	if(root->m_pLeft == NULL){//root为最小
		*min = root;
		*minPar = NULL;
		return;
	}
	*min = root->m_pLeft;
	*minPar = root;
	while((*min)->m_pLeft != NULL){
		*minPar = (*minPar)->m_pLeft;
		*min = (*min)->m_pLeft;
	}
	return;
}

int main()
{
	struct BSTreeNode * min=NULL,* minPar=NULL,*root=NULL;
	int	i;
	struct BSTreeNode node[7];

	node[0].m_nValue = 10;
	node[0].m_pLeft = &node[1];
	node[0].m_pRight= &node[2];
	node[1].m_nValue = 6;
	node[1].m_pLeft = &node[3];
	node[1].m_pRight= &node[4];
	node[2].m_nValue = 14;
	node[2].m_pLeft = &node[5];
	node[2].m_pRight= &node[6];
	node[3].m_nValue = 4;
	node[3].m_pLeft = NULL;
	node[3].m_pRight= NULL;
	node[4].m_nValue = 8;
	node[4].m_pLeft = NULL;
	node[4].m_pRight= NULL;
	node[5].m_nValue = 12;
	node[5].m_pLeft = NULL;
	node[5].m_pRight= NULL;
	node[6].m_nValue = 16;
	node[6].m_pLeft = NULL;
	node[6].m_pRight= NULL;
	cur = NULL;
	root = &node[0];
	while(1){
		getMin(root,&min,&minPar);
		min->m_pLeft = cur;
		if(cur != NULL)
			cur->m_pRight = min;
		cur = min;	//错误2		

		if(minPar!=NULL)
			minPar->m_pLeft = min->m_pRight;
		else{			//min 为 root
			root = min->m_pRight;
			if(root == NULL){
				break;
			}
		}		
	}
	for(i=0;i<7;i++){
		printf("%d ",cur->m_nValue);
		if(cur->m_pLeft != NULL)
			cur = cur->m_pLeft;
	}
	printf("\n");
	for(i=0;i<7;i++){
		printf("%d ",cur->m_nValue);
		cur = cur->m_pRight;
	}
	getchar();
	return 1;
}

2.寻找指定和路径

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

例如 输入整数22和如下二元树
  10   
  / /   
  5 12   
  / /   
  4 7
则打印出两条路径：10, 12和10, 5, 7。

二元树节点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree
{

int m_nValue; // value of node

BinaryTreeNode *m_pLeft; // left child of node

BinaryTreeNode *m_pRight; // right child of node
};

分析：

    这题像极了POJ 1154，不同在于：

1此题为二叉树，由于他制可能由上到下依次遍历左右子树，所以不需要额外的数组去标记访问状态

2需要记录路径，这里用到了回溯的一个小技巧。 
//二叉树 DFS
//45分钟
//错了一次 DFS如何回溯没有想清楚
#include <stdio.h>
#include <string.h>
#define SUM 22
struct BSTreeNode
{
	int m_nValue; 					// value of node
	struct BSTreeNode *m_pLeft; 	// left child of node	//错误1
	struct BSTreeNode *m_pRight; 	// right child of node
}; 
int idx;
int path[100];

void dfs(struct BSTreeNode *cur)
{
	int i;
	int sum=0;
	
	path[idx++] = cur->m_nValue;	//搜索某一个点
	for(i=0;i<idx;i++)
		sum += path[i];
	if(sum >= SUM){
		if(sum == SUM){
			for(i=0;i<idx;i++)
				printf("%d ",path[i]);
			printf("\n");
		}
		idx --;
		return;
	}
	if(NULL != cur->m_pLeft)
		dfs(cur->m_pLeft);
	if(NULL != cur->m_pRight)
		dfs(cur->m_pRight);
	idx--;							//回溯
	return;
}

int main()
{
	int i;
	struct BSTreeNode node[10];
	struct BSTreeNode *root = &node[0];

	node[0].m_nValue = 10;
	node[0].m_pLeft = &node[1];
	node[0].m_pRight= &node[2];
	node[1].m_nValue = 4;
	node[1].m_pLeft = &node[3];
	node[1].m_pRight= &node[4];
	node[2].m_nValue = 5;
	node[2].m_pLeft = &node[5];
	node[2].m_pRight= &node[6];
	node[3].m_nValue = 4;
	node[3].m_pLeft = NULL;
	node[3].m_pRight= NULL;
	node[4].m_nValue = 2;
	node[4].m_pLeft = &node[7];
	node[4].m_pRight= NULL;
	node[5].m_nValue = 5;
	node[5].m_pLeft = NULL;
	node[5].m_pRight= NULL;
	node[6].m_nValue = 1;
	node[6].m_pLeft = &node[8];
	node[6].m_pRight= &node[9];
	node[7].m_nValue = 2;
	node[7].m_pLeft = NULL;
	node[7].m_pRight= NULL;
	node[8].m_nValue = 2;
	node[8].m_pLeft = NULL;
	node[8].m_pRight= NULL;
	node[9].m_nValue = 3;
	node[9].m_pLeft = NULL;
	node[9].m_pRight= NULL;
	//idx = 1;
	//path[0] = root->m_nValue;
	dfs(root);
	return 1;
}

3. 判断后续遍历

输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
  8
  / /
  6 10
  / / / /
  5 7 9 11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。

//bsTree,判断后序遍历
//15分钟，错1次
//for循环中，第二项应该用逻辑符而不是逗号
#include <stdio.h>

int arr[10]={3,5,7,6,9,12,11,10,8};
int len = 9;
char flag = 1;

void isPostOrder(int idx)
{
	int idx1 = idx-1; //左子树的根节点存储值
	int i;

	if(!flag || idx<0)
		return;
	while(arr[idx1] > arr[idx]){	//找到左子树，若没有则idx1为负
		idx1--;
	}
	for(i=idx1-1;i>=0 && idx1>=0;i--){//判断左子树中是否有大于当前root的值
		if(arr[i] >= arr[idx]){
			flag = 0;
			return;
		}
	}
	isPostOrder(idx-1);	//递归第一个子树（若两个子树则为左，一个子树不固定）
	if(idx1 != idx-1 && idx1>=0)//判断是否有第二个子树
		isPostOrder(idx1);
	return;
}
int main()
{
	isPostOrder(8);
	if(!flag)
		printf("no\n");
	else
		printf("yes\n");
	getchar();
	return 1;
}

4 找出单向链表中的倒数第K个结点

比较容易想出解决方法，两个指针，距离为K，同时向后依次移动。时间复杂度为O(N)

5 求二叉搜索树的镜像

输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。   
例如输入：
  8
  / /
  6 10
 // //
5 7 9 11

输出：
  8
  / /
 10 6
 // //
11 9 7 5

定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
{
  int m_nValue; // value of node
  BSTreeNode *m_pLeft; // left child of node
  BSTreeNode *m_pRight; // right child of node
};

//二叉树 递归求镜像
//10分钟 
//一次通过
#include <stdio.h>
#include <string.h>

struct BSTreeNode
{
	int m_nValue; 					// value of node
	struct BSTreeNode *m_pLeft; 	// left child of node	//错误1
	struct BSTreeNode *m_pRight; 	// right child of node
}; 

void mirroritify(struct BSTreeNode *root)
{
	struct BSTreeNode *left;
	
	if(NULL==root->m_pLeft && NULL==root->m_pRight)
		return;
	mirroritify(root->m_pLeft);
	mirroritify(root->m_pRight);
	left = root->m_pLeft;
	root->m_pLeft = root->m_pRight;
	root->m_pRight = left;
	return;
}

int main()
{
	int i;
	struct BSTreeNode node[10];
	struct BSTreeNode *root = &node[0];

	node[0].m_nValue = 8;
	node[0].m_pLeft = &node[1];
	node[0].m_pRight= &node[2];
	node[1].m_nValue = 6;
	node[1].m_pLeft = &node[3];
	node[1].m_pRight= &node[4];
	node[2].m_nValue = 10;
	node[2].m_pLeft = &node[5];
	node[2].m_pRight= &node[6];
	node[3].m_nValue = 5;
	node[3].m_pLeft = NULL;
	node[3].m_pRight= NULL;
	node[4].m_nValue = 7;
	node[4].m_pLeft = NULL;
	node[4].m_pRight= NULL;
	node[5].m_nValue = 9;
	node[5].m_pLeft = NULL;
	node[5].m_pRight= NULL;
	node[6].m_nValue = 11;
	node[6].m_pLeft = NULL;
	node[6].m_pRight= NULL;
	
	mirroritify(root);
	return 1;
}



相关推荐