【数据结构】二叉树部分面试题解法
发布时间：2020-12-15 05:56:05 所属栏目：安全 来源：网络整理
导读：1.问题描述： 根据给定的二叉树前序中序遍历结果，重建出这颗二叉树。例如：前序遍历结果：1，2，3，4，5，6。中序遍历结果：3，2，4，1，6，5。 2.问题分析： 我们知道，前序遍历的顺序是：当前结点，左子树，右子树。那么，前序遍历的第一个数字就是根节点
1.问题描述：
根据给定的二叉树前序中序遍历结果，重建出这颗二叉树。例如：前序遍历结果：1，2，3，4，5，6。中序遍历结果：3，2，4，1，6，5。
2.问题分析：
我们知道，前序遍历的顺序是：当前结点，左子树，右子树。那么，前序遍历的第一个数字就是根节点。而中序遍历的顺序是：左子树，当前结点，右子树。所以，对于中序序列来说，根节点的左右分别就是左子树的结点和右子树的结点。故，我的做法是：用前序的第一个数建立根节点，从中序中找到前序序列的第一个数的下标，得到中序和前序左子树和右子树的结点序列，拿到了左右子树的前中序序列，那么和之前一样的方法再去建立左右子树。
3.源码：#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
template<class T>
struct Node
{
T _value;
Node<T>* _left;
Node<T>* _right;
Node(T value)
:_value(value),_left(NULL),_right(NULL)
{}
};
template<class T>
class Rebuild
{
public:
typedef Node<T> Node;
Rebuild(vector<T> InOrder,vector<T> PrevOrder)
{
assert(InOrder.size() == PrevOrder.size());
assert(InOrder.size() != 0);
_root = new Node(PrevOrder[0]);
if (InOrder.size() == 1)
return;
_root=_Rebulid(InOrder,PrevOrder,_root);
}
void PrevOrder()
{
_PrevOrder(_root);
}
protected:
void _PrevOrder(Node* root)
{
if (root == NULL)
return;
cout << root->_value<<" ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
Node* _Rebulid(vector<T>InOrder,vector<T>PrevOrder,Node*& root)
{
if (InOrder.size() == 0)
return NULL;
root = new Node(PrevOrder[0]);
size_t i = 0;
for (; i < InOrder.size(); i++) //找到中序数组里根节点的位置
{
if (InOrder[i] == PrevOrder[0])
break;
}
vector<T> InOrderLeft;
vector<T> InOrderRight;
vector<T> PrevOrderLeft;
vector<T> PrevOrderRight;
size_t j = 0;
for (; j<i; j++)
{
InOrderLeft.push_back(InOrder[j]);
PrevOrderLeft.push_back(PrevOrder[j + 1]);
}
for (size_t k = i + 1; k < InOrder.size(); k++)
{
InOrderRight.push_back(InOrder[k]);
PrevOrderRight.push_back(PrevOrder[k]);
}
root->_left = _Rebulid(InOrderLeft,PrevOrderLeft,root->_left);
root->_right = _Rebulid(InOrderRight,PrevOrderRight,root->_right);
return root;
}
private:
Node* _root;
};
void TestRebuild()
{
int prev[] = { 1,2,3,4,5,6 };
vector<int> PrevOrder(prev,prev+6);
int in[] = { 3,1,6,5 };
vector<int> InOrder(in,in + 6);
Rebuild<int> rb(InOrder,PrevOrder);
rb.PrevOrder();
}
1.问题描述：
求二叉树中最远的两个节点的距离。
2.问题分析：
首先要明确，不能单单去把根节点左右的距离加起来就行。万一是下图这种情况那就有问题了。
所以，我的做法是。后续遍历这颗二叉树，用distence变量记住每一个结点左右树距离的最大值。最后返回即可。
3.源码：#pragma once
#include<iostream>
using namespace std;
//普通二叉树寻找最远的两个结点的距离
template<class t>
struct binarytreenode
{
binarytreenode(t value = 0)
:_value(value),_right(NULL)
{}
t _value;
binarytreenode<t>* _left;
binarytreenode<t>* _right;
};
template<class t>
class binarytree
{
public:
typedef binarytreenode<t> node;
binarytree()
{}
binarytree(t* a,size_t size,const t& invalid)
{
size_t index = 0;
_root = _creattree(a,size,index,invalid);
}
binarytree(const binarytree<t>& bt)
{
_root = _copy(bt._root);
}
binarytree<t>& operator=(binarytree<t>& bt)
{
if (this != &bt)
{
binarytree<t> tmp(bt);
swap(tmp._root,_root);
}
}
~binarytree()
{
_root = _distory(_root);
}
node* Find(const t& n)
{
return _Find(_root,n);
}
int FindFarthestTwoNode()
{
int distence = 0;
_FindFarthestTwoNode(_root,distence);
return distence;
}
protected:
int _FindFarthestTwoNode(node* root,int& distence)
{
if (NULL == root)
{
distence = 0; //递归到空结点把上一个结点的左右最大距离清为0
return 0;
}
if (root->_left == NULL && root->_right == NULL)
{
return 0;
}
int leftd=_FindFarthestTwoNode(root->_left,distence)+1;
int rightd=_FindFarthestTwoNode(root->_right,distence)+1;
distence = (distence > (leftd + rightd) ? distence : (leftd + rightd)); //更新distence
return leftd > rightd ? leftd : rightd;
}
node* _Find(node* root,const t& n)
{
if (root == NULL)
return NULL;
if (root->_value == n)
return root;
node* left = _Find(root->_left,n);
node* right = _Find(root->_right,n);
return left ? left : right;
}
node* _distory(node* root)
{
if (root)
{
_distory(root->_left);
_distory(root->_right);
node* del = root;
delete del;
}
return root;
}
node* _creattree(t*a,size_t& index,const t& invalid)
{
node* root = NULL;
if ((index < size) && (a[index] != invalid))
{
root = new node(a[index]);
root->_left = _creattree(a,++index,invalid);
root->_right = _creattree(a,invalid);
}
return root;
}
node* _copy(node* copyroot)
{
node* root = NULL;
if (copyroot != NULL)
{
root = new node(copyroot->_value);
root->_left = _copy(copyroot->_left);
root->_right = _copy(copyroot->_right);
}
return root;
}
private:
node* _root;
};
void TestFindNearParent()
{
int array1[15] = { 1,'#',7,8 };
binarytree<int> bt(array1,15,'#');
cout<<bt.FindFarthestTwoNode();
}
1.问题描述：
判断一棵树是否是完全二叉树。
2.问题分析：
完全二叉树有什么特点呢？除最后一层外，其余每一层的结点都是满的，且最后一层结点不间断。如下图
做法很简单：层序遍历把树的所有结点（包括空结点）全部进入队列。然后挨个pop掉，如果碰到空的时候就判断队列中剩下的结点是否都为空，若此时队列中还有不为空的结点，则说明不是完全二叉树。 3.源码：#pragma once
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
template<class t>
struct binarytreenode
{
binarytreenode(t value = 0)
:_value(value),_root);
}
}
~binarytree()
{
_root = _distory(_root);
}
bool IsCompleteTree() //判断是否是完全二叉树
{
queue<node*> q;
q.push(_root);
node* cur = q.front();
while ((cur = q.front()) != NULL) //当前结点不为空则push进它的左右
{
q.push(cur->_left);
q.push(cur->_right);
q.pop();
}
while (!q.empty()) //到这里说明取到了一个空结点，判断剩下的是否有不为空的结点。
{
cur = q.front();
if (cur != NULL)
return false;
q.pop();
}
return true;
}
protected:
node* _distory(node* root)
{
if (root)
{
_distory(root->_left);
_distory(root->_right);
node* del = root;
delete del;
}
return root;
}
node* _creattree(t*a,invalid);
}
return root;
}
node* _copy(node* copyroot)
{
node* root = NULL;
if (copyroot != NULL)
{
root = new node(copyroot->_value);
root->_left = _copy(copyroot->_left);
root->_right = _copy(copyroot->_right);
}
return root;
}
private:
node* _root;
};
void TestIsCompleteTree()
{
int array[10] = { 1,6 };
int array1[15] = { 1,'#');
cout<<bt.IsCompleteTree();
}
1.问题描述：
求二叉树两个节点的最近公共父节点。
2.问题分析：
当这棵树是一个二叉搜索树的时候，可以利用二叉搜索树的性质。从根节点找，若当前结点比两个结点中小的那个大，比大的那个小。说明当前结点就是最近的公共父节点。若当前结点比传进来的两个数都大，说明公共父节点在当前结点的左树上，那么向左树去找；若比两个数都小，说明公共父节点在当前结点的右树上，向右树去找。
当这棵树是一颗普通的二叉树的时候，一种做法是保存找到两个结点的路径，存到两个链表里，再去找两个链表的第一个交点。这种方法简单粗暴，但是空间复杂度近似于O(n^2)。另一种方法是，递归去找传进来的两个结点，若找到了则返回。那么如果分别在当前结点的左右找到，那就返回当前结点，说明当前结点就是最近的公共父节点。若左右有一个为空，说明不为空的那个就是最近的公共父节点。
3.源码：#pragma once
#include<iostream>
using namespace std;
//二叉搜索树找最近的公共父节点
template<class K>
struct SelectBinaryTreeNode
{
typedef SelectBinaryTreeNode<K> Node;
K _key;
Node* _left;
Node* _right;
SelectBinaryTreeNode(const K& key)
:_key(key),_right(NULL)
{}
};
template<class K>
class SelectBinaryTree
{
public:
typedef SelectBinaryTreeNode<K> Node;
SelectBinaryTree()
{}
~SelectBinaryTree() //析构，递归实现
{
_Destory(_root);
}
bool Insert(const K& key) //非递归插入
{
if (NULL == _root)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = NULL;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key>key)
{
parent = cur;
cur = cur->_left;
}
else
return false;
}
if (parent->_key < key)
{
parent->_right = new Node(key);
}
else
parent->_left = new Node(key);
return true;
}
bool InsertR(const K& key) //递归插入
{
return _InsertR(_root,key);
}
Node* Find(const K& k)
{
return _FindR(_root,k);
}
K FindNearestParent(const K& key1,const K& key2)
{
Node* node1 = Find(key1);
Node* node2 = Find(key2);
if (node1 == NULL || node2 == NULL)
{
return -1;
}
K min = 0;
K max = 0;
if (key1 > key2)
{
min = key2;
max = key1;
}
else
{
min = key1;
max = key2;
}
Node* cur = _root;
while (cur)
{
if (cur->_key >= min && cur->_key <= max)
{
return cur->_key;
}
else if (cur->_key <= min && cur->_key <= max)
{
cur = cur->_right;
}
else
{
cur = cur->_left;
}
}
return -1;
}
protected:
Node* _FindR(Node* root,const K& key)
{
if (NULL == root)
return NULL;
if (root->_key == key)
return root;
else if (root->_key < key)
_FindR(root->_right,key);
else if (root->_key>key)
_FindR(root->_left,key);
}
bool _InsertR(Node*& root,const K& key)
{
if (NULL == root)
{
root = new Node(key);
return true;
}
if (root->_key < key)
return _InsertR(root->_right,key);
else if (root->_key>key)
return _InsertR(root->_left,key);
else
return false;
}
void _Destory(Node* root)
{
Node* cur = root;
while (cur)
{
Node* del = cur;
cur = cur->_right;
delete del;
}
}
private:
Node* _root;
};
void TestFindNearestParent()
{
SelectBinaryTree<int> sbt;
int a[] = { 5,8,9 };
for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
sbt.InsertR(a[i]);
}
cout << sbt.FindNearestParent(8,9) << endl;
}
普通二叉树寻找最近的父节点
template<class t>
struct binarytreenode
{
binarytreenode(t value = 0)
:_value(value),n);
}
t FindNearParent(const t& n1,const t& n2)
{
node* node1 = Find(n1);
node* node2 = Find(n2);
if (node1 == NULL || node2 == NULL) //若传过来的结点不在树内
{
throw std::invalid_argument("结点不在树内");
}
node* ret=_FindNearParent(_root,node1,node2);
return ret->_value;
}
protected:
node* _FindNearParent(node* root,node* n1,node*n2)
{
if (NULL == root)
return NULL;
if (root == n1 || root == n2) //找到了其中一个结点
{
return root;
}
node* left = _FindNearParent(root->_left,n1,n2);
node* right = _FindNearParent(root->_right,n2);
if (left&&right) //left和right都存在，说明结点分别在root的左右
{
return root;
}
return left ? left : right; //左右哪个不为空返回哪个，说明两个结点都在一侧
}
node* _Find(node* root,const t& n)
{
if (root == NULL)
return NULL;
if (root->_value == n)
return root;
node* left=_Find(root->_left,n);
node* right=_Find(root->_right,n);
return left ? left : right;
}
node* _distory(node* root)
{
if (root)
{
_distory(root->_left);
_distory(root->_right);
node* del = root;
delete del;
}
return root;
}
node* _creattree(t*a,invalid);
}
return root;
}
node* _copy(node* copyroot)
{
node* root = NULL;
if (copyroot != NULL)
{
root = new node(copyroot->_value);
root->_left = _copy(copyroot->_left);
root->_right = _copy(copyroot->_right);
}
return root;
}
private:
node* _root;
};
void TestFindNearParent()
{
int array1[15] = { 1,8 };
binarytree<int> bt(array1,'#');
try{
cout << bt.FindNearParent(0,8);
}
catch (exception &e)
{
cout << e.what() << endl;
}
}
1.问题描述：
将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
2.问题分析：
这个问题其实和二叉树的线索化有些类似，根据二叉搜索树的性质，中序遍历的结果就是一个有序的数组，所以我们中序去做。二叉树原来的左指向默认为双向链表的前驱指针，有指向默认为next指针。做法是：定义一个prev指针，递归去让prev的左指向当前结点，如若prev不为空，则prev的右指向当前结点，再去更新prev。要注意的是，二叉搜索树被转换成双向链表之后，它的析构函数必须要重新写，变成链表的析构，否则会导致栈溢出。
3.源码：#pragma once
#include<iostream>
using namespace std;
template<class K>
struct SelectBinaryTreeNode
{
typedef SelectBinaryTreeNode<K> Node;
K _key;
Node* _left;
Node* _right;
SelectBinaryTreeNode(const K& key)
:_key(key),_right(NULL)
{}
};
template<class K>
class SelectBinaryTree
{
public:
typedef SelectBinaryTreeNode<K> Node;
SelectBinaryTree()
{}
~SelectBinaryTree() //析构，递归实现
{
_Destory(_root);
}
void TodoubleLink() //二叉搜索树转化成双向链表
{
Node* prev = NULL;
_TodoubleLink(_root,prev);
Node* head = _root;
while (head->_left)
{
head = head->_left;
}
_root = head;
while (head)
{
cout << head->_key << " ";
head = head->_right;
}
cout << endl;
}
bool Insert(const K& key) //非递归插入
{
if (NULL == _root)
{
_root = new Node(key);
return true;
}
Node* cur = _root;
Node* parent = NULL;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key>key)
{
parent = cur;
cur = cur->_left;
}
else
return false;
}
if (parent->_key < key)
{
parent->_right = new Node(key);
}
else
parent->_left = new Node(key);
return true;
}
bool InsertR(const K& key) //递归插入
{
return _InsertR(_root,key);
}
protected:
Node* _TodoubleLink(Node* root,Node*& prev)
{
if (root == NULL)
return NULL;
Node* cur = root;
_TodoubleLink(cur->_left,prev);
cur->_left = prev;
if (prev)
prev->_right = cur;
prev = cur;
_TodoubleLink(cur->_right,prev);
return root;
}
bool _InsertR(Node*& root,key);
else
return false;
}
void _Destory(Node* root)
{
Node* cur = root;
while (cur)
{
Node* del = cur;
cur = cur->_right;
delete del;
}
}
private:
Node* _root;
};
void TestTodoubleLink()
{
int a[] = { 5,0 };
SelectBinaryTree<int> sbt;
for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
sbt.InsertR(a[i]);
}
sbt.TodoubleLink();
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |