二叉树的五道面试题

待我称王封你为后i 2022-07-14 06:14 168阅读 0赞

1、判断一棵树是否是完全二叉树；

2、求二叉树中最远两个结点的距离；

3、由前序和中序遍历序列重建二叉树 （前序序列：1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5）；

4、求二叉树两个结点的最近公共祖先；

5、将二叉搜索树转化成有序的双向链表；

**判断一棵树是否是完全二叉树**

要想判断一颗树是否是完全二叉树，你得先知道什么是完全二叉树。

**完全二叉树：**

①若树的高度为h，则除第h层，上面的h-1层都是达到最大个数。

②第h层的结点都集中在最左边。

当你知道了完全二叉树的性质，这道题就好做了。有很多种解法。这里我给出一种使用 **队列**的解法。

我们先看一下完全二叉树与非完全二叉树的区别：

![Image 1][]

![20161130084903124][]

我们可以看到， **将完全的二叉树的所有结点push到队列里之后，有连续的非NULL结点。中间没有NULL打断。而非完全二叉树非空结点之间右NULL打断。我们可以根据这一区别来判断一棵树是否是完全二叉树。**

代码：

**//队列法**

//队列法
    bool IsCompleteTree()
    {
    	if (_root == NULL)
    	{
    		return true;
    	}
    	Node* root = _root;
    	queue<Node*> q;//建立队列
    	q.push(root);//先将根节点入队列
    
    	//层序遍历，将结点依次入队列
    	while (1)
    	{
    		q.push(root->_left);
    		q.push(root->_right);
    		q.pop();
    		if (q.front() != NULL)
    		{
    			root = q.front();
    		}
    		else
    		{
    			break;//遇到空结点就退出循环
    		}
    
    	}
    	//遇到空结点，判断后面是否还有空结点
    	while (!q.empty())
    	{
    		Node* ret = q.front();
    		if (ret != NULL)
    		{
    			return false;
    		}
    		q.pop();
    	}
    	return true;
    }

还有一种时间空间复杂度较为复杂的解法，使用了递归。我将代码放到这里，感兴趣的可以研究下。

**递归法：**

//递归法
    bool IsCompleteTree()
    {
    	if (_root == NULL)
    	{
    		return true;
    	}
    	return __IsCompleteTree(_root);
    }
    //递归判断
    bool __IsCompleteTree(Node* root)
    {
    	if (root == NULL)
    	{
    		return true;
    	}
    	if (root->_left == NULL && root->_right != NULL)
    	{
    		return false;
    	}
    	//递归，求每一个节点的左右高度
    	int left = __GetHigh(root->_left) + 1;
    	int right = __GetHigh(root->_right) + 1;
    	if (left - right > 1)//当其中某个节点的左右高度差大于1的时候，就不满足完全二叉树
    	{
    		return false;
    	}
    	return __IsCompleteTree(root->_left) && __IsCompleteTree(root->_right);
    }

**求二叉树中最远两个结点的距离**

看到这个题，一般大家会有一个思想误区：最远的两个结点是左子树最深结点和右子树最深结点。不是！千万不要这样想！

**最远结点，即为相距路径最长的两个结点**，例如下面两种情况：

![20161130090037764][]

![Image 1][]

**最优解法**：利用递归（ 后序递归），划分子问题。

**子问题模型**：传一个全局变量Max（最远距离），初值设为0，传参类型为传引用。求取当前结点cur左右子树的深度并进行比较，返回较深的子树的深度的值。在返回前，将左右子树的深度相加求的和，与Max进行比较，若和大于Max，将和的值赋给Max。

例如：

![Image 1][]

![20161130090153315][]

**我们在写代码的时候不要递归到一个结点就对其左右子树求高度。这样会大大增加工作量，降低了程序的效率。采用后序递归，先递归左子树，再递归右子树。将子树高度层层返回，会是最优的解法。令时间复杂度达到O(N)。**

代码：

//求二叉树中最远两个结点的距离
    size_t GetMaxLength()
    {
    	size_t Max = 0;
    	__MaxLength(_root, Max);
    	return Max;
    }
    //求二叉树中最远两个结点的距离
    size_t __MaxLength(Node* root, size_t &Max)
    {
    	if (root == NULL)
    	{
    		return 0;
    	}
    	if (root->_left == NULL && root->_right == NULL)
    	{
    		return 0;
    	}
    	size_t left = __MaxLength(root->_left, Max) + 1;//求左子树高度
    	size_t right = __MaxLength(root->_right, Max) + 1;//求右子树高度
    
    	if (Max < left + right)//每次判断Max与left+right的大小
    	{
    		Max = left + right;
    	}
    	if (left > right)// 返回左右子树最深的高度
    	{
    		return left;
    	}
    	else
    	{
    		return right;
    	}
    }

**由前序和中序遍历序列重建二叉树 （前序序列：1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5）**

想要根据前序和中序遍历序列重建二叉树，首先要知道这两个序列的性质。

**前序序列**：第一个数据为根结点。

**中序序列**：根结点值左侧数据均为左子树，根结点值右侧数据均为右子树。

现在我们来看这两个序列：

![20161130090600641][]

根绝这个思路，最好的解题方式就是 **递归**。划分子问题。

**子问题模型**：由前序找到根结点，由后序取重建这个跟结点的左右子树。

代码：

//由前序和中序遍历序列重建二叉树 （前序序列：1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5）
    void ReCreateTree(const T* prev, const T* In, const int size)
    {
    	assert(prev);
    	assert(In);
    	int index = 0;
    	_root = __ReCreatrTree(0, size, size, prev, In, index);
    }
    //由前序和中序遍历序列重建二叉树 （前序序列：1 2 3 4 5 6 - 中序序列:3 2 4 1 6 5）
    //begin end为后序的区间
    //size为序列元素的数量
    //prev In 分别是指向前序中序序列的指针
    //index为下标（前序序列中）
    Node* __ReCreatrTree(int begin, int end, int size, const T* prev, const T* In, int &index)
    {
    	if (index < size)
    	{
    		Node* root = NULL;
    
    		root = new Node(prev[index]);
    		int div = 0;
    		//前序第一个结点为根节点
    		for (int i = begin; i <= end; ++i)
    		{
    			//在后序中找根节点
    			if (In[i] == prev[index])
    			{
    				div = i;
    				break;
    			}
    		}
    		//划分区间 左右两部分
    		if (begin <= div - 1)
    		{
    			root->_left = __ReCreatrTree(begin, div - 1, size, prev, In, ++index);
    		}
    		if (div + 1 <= end)
    		{
    			root->_right = __ReCreatrTree(div + 1, end, size, prev, In, ++index);
    		}
    
    		return root;
    	}
    	return NULL;
    }

**求二叉数两个结点的最近公共祖先**

求二叉树两个结点的最近公共祖先算是一道常考的面试题。此题只给出了二叉树这个大范围，并没有规定是哪一种二叉树，所以我们可以根据不同的情况给出不同的算法。（到时可以向面试官问清楚这一点，没准儿会加分！）

我们可以将其分为三种情况：

**①二叉搜索树（BST:BinarySeachTree）**

二叉搜索树是一种比较特殊的情况，所以我们可以根据它的结构特点对它进行“特殊对待”。

二叉搜索树特点：左孩子的值 < 父亲的值 < 右孩子的值。整棵树中没有值重复的结点。

如图为一棵二叉搜索树：

![20161130091444334][]

假设现在有两个值，求它们的最近公共祖先。因为是二叉搜索树，没有重复值，所以这两个值肯定一个大，一个小。我们将大的命名为max，小的命名为min。设他们的最近公共祖先叫LastParent。设当前结点为cur

根据二叉搜索树的性质，max，min，cur这三个值肯定满足下面性质中的某一条：

**①cur>max >min**

说明LastParent在当前结点的左子树中。

**②cur< min<max**

说明LastParent再当前结点的右子树中。

**③min <=cur<=max**

说明cur就是LastParent。

例如 ：

![20161130091627785][]

![20161130090126498][]

**代码1：**

**利用循环**

Node* FindParentBST(Node* child1, Node* child2)
    {
    	if (_root == NULL)
    	{
    		return NULL;
    	}
    	if (child == NULL || child2 == NULL)
    	{
    		return NULL;
    	}
    	Node* cur = _root;
    	while (1)
    	{
    		//判断当前节点的值是不是在区间内
    		if (cur->_data >= child1->_data && cur->_data <= child2->_data ||
    			cur->_data >= child2->_data && cur->_data <= child1->_data)
    		{
    			return cur;
    		}
    		//当不在区间内，并且大于其中某一个值，那cur的值一定大于所有值
    		//LastParnet在左子树
    		else if (cur->_data >= child1->_data)
    		{
    			cur = cur->_left;
    		}
    		// 否则在右子树
    		else
    		{
    			cur = cur->_right;
    		}
    	}
    }

**代码2：**

**利用递归**

Node* FindParentBST(Node* child1, Node* child2)
    {
    	if (_root == NULL)
    	{
    		return NULL;
    	}
    	return __FindParentBST(_root, child1, child2);
    }
    Node* __FindParentBST(Node* root, Node* child1, Node* child2)
    {
    	if (!root || !child1 || !child2)
    	{
    		return NULL;
    	}
    	//当root的值大于两个孩子的最大值时
    	if (root->_data > max(child1->_data, child2->_data))
    	{
    		return __FindParentBST(root->_left, child1, child2);
    	}
    	//当root 的值小于两个孩子的最小值时
    	else if (root->_data < min(child1->_data, child2->_data))
    	{
    		return __FindParentBST(root->_right, child1, child2);
    	}
    	//在区间内，root即为最近公共祖先，返回root
    	else
    	{
    		return root;
    	}
    }

**②有指向父亲结点的指针的“三叉树”**

结点结构为：

template<typename T>
    struct TreeNode
    {
    	T _data;
    	TreeNode<T>* _left;//指向左孩子的指针
    	TreeNode<T>* _right;//指向右孩子指针
    	TreeNode<T>* _parent;//指向父亲指针
    
    	TreeNode(const T& data = T())
    		:_data(data)
    		, _left(NULL)
    		, _right(NULL)
    	{}
    };

当每个结点除了有指向左右孩子的指针，再有一个指向它父亲的指针时，处理这个问题就简单多了。

先看图：

![20161130092456910][]

![20161130092511086][]

![20161130092520755][]

这样，我们就将求最近公共祖先的问题转化成了求两个相交链表的交点的问题。用栈或者计数法都行。归根结底都要统计一下两个单链表结点的长度length1，length2，让长的单链表先走 |length1-length2| 个结点，再让两个链表一起走，直到相遇，相遇点就是交点（ 最近公共祖先）。

![20161130092711227][]

** 代码：**

//有父亲指针
    Node* FindParentH(Node* child1, Node* child2)
    {
    	if (_root == NULL)
    	{
    		return NULL;
    	}
    	if (child1&&child2)
    	{
    		Node* cur1 = child1;
    		Node* cur2 = child2;
    		size_t sz1 = 0;
    		size_t sz2 = 0;
    		while (cur1 != _root)//计算链表1的长度
    		{
    			cur1 = cur1->_parent;
    			sz1++;
    		}
    		while (cur2 != _root)//计算链表2的长度
    		{
    			cur2 = cur2->_parent;
    			sz2++;
    		}
    		cur1 = child1;
    		cur2 = child2;
    		int n = sz1 - sz2;//求出长度差 让长的先走
    		if (sz1 > sz2)
    		{
    			while (n > 0)
    			{
    				cur1 = cur1->_parent;
    				n--;
    			}
    		}
    		else
    		{
    			n = -n;
    			while (n > 0)
    			{
    				cur2 = cur2->_parent;
    				n--;
    			}
    		}
    		while (cur1 != cur2)//相遇点即为交点
    		{
    			cur1 = cur1->_parent;
    			cur2 = cur2->_parent;
    		}
    		return cur1;
    	}
    	else
    	{
    		return NULL;
    	}
    }

**③普通的二叉树，没有指向父亲结点的指针。**

如果是普通的二叉树，我们就没有了特殊条件可以利用。只能挨个遍历去找。这里有两种解题方法。

**第一种解法：用两个栈**

（其实结构类似于栈的都可以如vector，list等。）

现在我们有两个结点，Node1,Node2。用两个栈分别去他们二叉树内的位置，并保存经过的结点。最后做对比找出最近公共祖先结点。

过程如图:

![20161130093027230][]

同理，我们得到第二个寻找5的栈，然后对比 。

![20161130093104481][]

**时间复杂度分析**：最坏的情况是二叉树的所有节点都遍历一遍，所以最坏时间复杂度为O(N)。

**空间复杂度分析**：开辟了两个栈，有空间损耗。 最差情况为要找的结点再最深处lgN，开辟了两个栈，空间复杂度为2O(lg

N)，再加上二叉树本身的空间复杂度O(N)，总的空间复杂度为O(N)+2O(lgN)

可以看到，这种方法空间损耗还是比较大的，面试官会要求你写出空间损耗更少的更优算法。看 第二种解法。

**代码1：**

**用两个栈**

Node* FindParentS(const T& t1, const T& t2)
    {
    	if (_root == NULL)
    	{
    		return false;
    	}
    	//建立两个栈
    	stack<Node*> s1;
    	stack<Node*> s2;
    
    	Node* cur = _root;
    	Node* prev = NULL;
    	s1.push(cur);
    	while (!s1.empty())
    	{
    		while (cur&& cur->_data != t1)
    		{
    			cur = cur->_left;
    			if (cur)
    			{
    				s1.push(cur);
    			}
    		}
    		if (cur&&cur->_data == t1)
    		{
    			break;
    		}
    		cur = s1.top();
    		if (prev == cur)
    		{
    			s1.pop();
    			cur = s1.top();
    		}
    		prev = cur;
    		cur = cur->_right;
    	}
    	if (s1.empty())
    	{
    		return NULL;
    	}
    	cur = _root;
    	prev = NULL;
    	s2.push(cur);
    	while (!s2.empty())
    	{
    		while (cur  && cur->_data != t2)
    		{
    			cur = cur->_left;
    			if (cur)
    			{
    				s2.push(cur);
    			}
    
    		}
    		if (cur&&cur->_data == t2)
    		{
    			//s2.push(cur);
    			break;
    		}
    		cur = s2.top();
    		if (prev == cur)
    		{
    			s2.pop();
    			cur = s2.top();
    		}
    		prev = cur;
    		cur = cur->_right;
    	}
    	if (s2.empty())
    	{
    		return NULL;
    	}
    
    	int n = s1.size() - s2.size();
    	if (s1.size() > s2.size())
    	{
    		while (n)
    		{
    			s1.pop();
    			n--;
    		}
    	}
    	else
    	{
    		n = -n;
    		while (n)
    		{
    			s2.pop();
    			n--;
    		}
    	}
    	while (s1.top() != s2.top())
    	{
    		s1.pop();
    		s2.pop();
    	}
    	return s1.top();
    }

**第二种解法：用递归。**

假设我们要找Node1，Node2的最近公共祖先。

**递归思想：**

①划分成小问题，对每一个节点cur进行左右递归。寻找Node1，Node2。当我们找到一个结点等于这两个值任意一个时，就返回当前节点cur。找不到则返回NULL。

②在cur的左右都寻找完后，会得到两个返回值ret1 （递归cur左子树得到的返回值），ret2（递归cur右子树的到的返回值）。

③如果ret1和ret2都不为空，说明Node1，Node2，一个存在于cur的左子树，一个存在于cur的右子树。cur就是最近公共祖先。

④如果其中一个为空，说明Node1与Node2中只有一个存在于以cur为根节点的二叉树中，返回ret1与ret2中不为空的一个。

⑤如果都为空，则说明Node1，Node2都不存在于以cur为根节点的二叉树中，返回NULL。

如图：

![20161130093706591][]

**时间复杂度分析：**对二叉树所有的结点都遍历了一遍，时间复杂度为O（N）

**空间复杂度分析**：没有开辟额外的辅助空间，只有建立二叉树与递归的空间占用。空间复杂度为O(N)+O(lgN)

**代码2：**

**递归**

//用递归
    //从根节点开始递归，遍历左子树右子树，分解成子问题。当root的左右等于任意某一值时，就返回。
    Node* FindParent(const Node* child1, const Node* child2)
    {
    	if (_root == NULL)
    	{
    		return NULL;
    	}
    	if (child1&&child2)
    	{
    		return __FindParent(_root, child1, child2);
    	}
    	else
    	{
    		return NULL;
    	}
    }
    Node* __FindParent(Node* root, const Node* child1, const Node* child2)
    {
    	if (root == NULL)
    	{
    		return NULL;
    	}
    	if (root == child1 || root == child2)
    	{
    		return root;
    	}
    	//递归左子树
    	Node* ret1 = __FindParent(root->_left, child1, child2);
    	//递归右子树
    	Node* ret2 = __FindParent(root->_right, child1, child2);
    	//当两个返回值都不为空时返回当前结点
    	if (ret1&&ret2)
    	{
    		return root;
    	}
    	//否则返回不为空的返回值
    	else
    	{
    		Node* ret = (ret1 != NULL ? ret1 : ret2);
    		return ret;
    	}
    }

**将二叉搜索树转化成有序的双向链表**

对于学过线索二叉树的同学来说，这道题再简单不过了。因为这道题与中序线索化思想相同，更比它简单。

问题分析就不说了，利用前序递归，一遍遍历就搞定。

![20161130100755903][]

**代码：**

//将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
    Node* TreeToList()
    {
    	if (_root == NULL)
    	{
    		return NULL;
    	}
    
    	Node* prev = NULL;
    	__TreeToList(_root, prev);
    	Node* cur = _root;
    	while (cur->_left)
    	{
    		cur = cur->_left;
    	}
    	return cur;
    }
    bool __TreeToList(Node* root, Node*& prev)
    {
    	static Node* prev = NULL;
    	if (root == NULL)
    	{
    		return false;
    	}
    	__TreeToList(root->_left, prev);
    	root->_left = prev;
    	if (prev)
    	{
    		prev->_right = root;
    	}
    	prev = root;
    	__TreeToList(root->_right, prev);
    	return true;
    }

[Image 1]: 
[20161130084903124]: /images/20220714/3900ea672d504d95899d34ebf2a67622.png
[20161130090037764]: /images/20220714/9c9770e423314af68fb82f879aa117e7.png
[20161130090153315]: /images/20220714/c1f0a9fba7c94741a9421bbdc273ae34.png
[20161130090600641]: /images/20220714/8446f79740ab46508bcb3934627227ea.png
[20161130091444334]: /images/20220714/d7e88421b6d44c9d90c9534bd69ffb6e.png
[20161130091627785]: /images/20220714/512f41577ae14a31af0c5237e2493eff.png
[20161130090126498]: /images/20220714/79a4a90f77954cedbe8c1069271f04b0.png
[20161130092456910]: /images/20220714/62cad37ca11749e39b8ccfaac8e48fe1.png
[20161130092511086]: /images/20220714/72faaa067d0946a5a4fb7224d3273b54.png
[20161130092520755]: /images/20220714/2c2c083e00434fafaad2affc43a16f07.png
[20161130092711227]: /images/20220714/ae6b2d08408d4e1585e58817f9ce35ed.png
[20161130093027230]: /images/20220714/c459f51d94b24557ad6a79fb1ef5421d.png
[20161130093104481]: /images/20220714/8e53d5c8504b49e9a0bfa84a00c35135.png
[20161130093706591]: /images/20220714/87c900dda4254c64b70272dbecb57e8c.png
[20161130100755903]: /images/20220714/ce6f07211478418eb27bb8f2a89e7ebe.png