面试题精解之一：二叉树

淩亂°似流年 2022-08-28 02:45 94阅读 0赞

转自：[http://www.cppblog.com/flyinghearts/archive/2012/02/28/166713.html\#\_Toc317966395][http_www.cppblog.com_flyinghearts_archive_2012_02_28_166713.html_Toc317966395]

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

2 判断二叉树是否平衡二叉树  
3 指定二叉树，给定两节点求其最近共同父节点  
4 二叉树的广度遍历、逐层打印二叉树节点数据、只打印某层节点数据  
5 在二叉树中找出和（叶子到根节点路径上的所有节点的数据和）为指定值的所有路径。  
6 将二叉查找树转为有序的双链表  
7 求二叉树的镜像  
8 二叉树前序、中序、后序遍历的非递归实现  
9 计算二叉树高度的非递归实现  
10 连接二叉树同一层上的结点  
  
  
特别说明:  
本文中二叉树结构定义为：  
struct Node\{  
Node\* left;  
Node\* right;  
int data;  
\};  
  
定义：空二叉树的高度为-1，只有根节点的二叉树高度为0，根节点在0层，深度为0。  
  
1. 求二叉树中相距最远的两个节点之间的距离  
  
两个节点的距离为两个节点间最短路径的长度。  
求两节点的最远距离，实际就是求二叉树的直径。假设相距最远的两个节点分别为A、B，它们的最近共同父节点（允许一个节点是其自身的父节点）为C，则A到B的距离 = A到C的距离 + B到C的距离。  
节点A、B分别在C的左右子树下（假设节点C的左右两子树均包括节点C），不妨假设A在C的左子树上，由假设“A到B的距离最大”，先固定B点不动（即B到C的距离不变），根据上面的公式，可得A到C的距离最大，即点A是C左子树下距离C最远的点，即：  
  
A到C的距离 = C的左子树的高度。  
同理， B到C的距离 = C的右子树的高度。  
  
因此，本问题可以转化为：“二叉树每个节点的左右子树高度和的最大值”。

static int tree_height(const Node* root, int& max_distance)
    {
    	const int left_height = root->left ? tree_height(root->left,  max_distance) + 1 : 0;
    	const int right_height = root->right ? tree_height(root->right, max_distance)  + 1 : 0;
    
    	const int distance = left_height + right_height;
    	if (max_distance < distance) 
    	{
    		max_distance = distance;	
    	}
    
    	return (left_height > right_height ? left_height : right_height);
    }
    
    int tree_diameter(const Node* root)
    {
    	int max_distance = 0;
    
    	if (root != NULL) 
    	{
    		tree_height(root, max_distance);	
    	}
    
    	return max_distance;
    }

2. 判断二叉树是否平衡二叉树  
  
根据平衡二叉树的定义：每个结点的左右子树的高度差小等于1，只须在计算二叉树高度时，同时判断左右子树的高度差即可。

static int tree_height(const Node* root, bool& balanced)
    {
    	const int left_height = root->left ? tree_height(root->left, balanced) + 1 : 0;
    	if (!balanced)
    	{
    		return 0;
    	}
    
    	const int right_height = root->right ? tree_height(root->right, balanced) + 1 : 0;
    	if (!balanced) 
    	{
    		return 0;
    	}
     
    	const int diff = left_height - right_height;
    	if (diff < -1 || diff > 1) 
    	{
    		balanced = false; 
    	}
    
    	return (left_height > right_height ? left_height : right_height);
    }
    
    bool is_balanced_tree(const Node* root)
    {
    	bool balanced = true;
    	if (root != NULL)
    		tree_height(root, balanced);
    
    
    	return balanced;
    }

3 指定二叉树，给定两节点求其最近共同父节点  
  
  
遍历二叉树时，只有先访问给定两节点A、B后，才可能确定其最近共同父节点C，因而采用后序遍历。  
  
  
可以统计任一节点的左右子树“是否包含A、B中的某一个”（也可以直接统计“包含了几个A、B”）。当后序遍历访问到某个节点D时，可得到三条信息：节点D是否是A、B两节点之一、其左子树是否包含A、B两节点之一、其右子树是否包含A、B两节点之一。当三条信息中有两个为真时，就可以确定节点D的父节点（或节点D，如果允许一个节点是自身的父节点的话）就是节点A、B的最近共同父节点。另外，找到最近共同父节点C后应停止遍历其它节点。

// ① 允许节点是其自身的父节点(若B是A的孩子，A、B的最近共同父节点为A)：
    // 代码1：
    static bool lca(const Node* root, const Node* va, const Node* vb, const Node*& result)
    {
    	const bool left = root->left ? lca(root->left, va, vb, result) : false;
    	if (result) 
    	{
    		return false; // 剪枝，随便返回一个值
    	}
    
    	const bool right = root->right ? lca(root->right, va, vb, result) : false;
    	if (result) 
    	{
    		return false;	
    	}
    	
    	// 由于va可能等于vb，不要写成： const int mid = (root == va) | (root == vb);
    	const int mid = (root == va) + (root == vb); 
    	
    	int ret = left + right + mid;
    
    	if (ret == 2) result = root;
    
    	return (bool)ret;
    }
    
    const Node* lca(const Node* root, const Node* va, const Node* vb)
    {
    	const Node* result = NULL;
    
    	if (root)
    	{
    		lca(root, va, vb, result);	
    	}
    	
    	return result;
    }

上面的代码中需要特别注意的是：判断所访问时节点是否是两节点A、B时要写成  
  
const int mid = (root == va) + (root == vb);  
  
而不是： const int mid = (root == va) | (root == vb);  
  
这样当va等于vb时，可以得到正确结果。  
  
  
若采用第二种方法，代码可以改写为：

//代码2：
    static int lca(const Node* root, const Node* va, const Node* vb, const Node*& result)
    {
    	const int N = 2;
    	const int left = root->left ? lca(root->left, va, vb, result) : 0;
    
    	if (left == N)
    	{
    		return N;
    	} 
    
    	const int right = root->right ? lca(root->right, va, vb, result) : 0;
    	if (right == N) 
    	{
    		return N;
    	}
    
    	const int mid = (root == va) + (root == vb);
    	const int ret = left + right + mid;
    	if (ret == N) 
    		result = root;
    
    	return ret;
    }
    
    const Node* lca(const Node* root, const Node* va, const Node* vb)
    {
    	const Node* result = NULL;
    
    
    	if (root != NULL)
    		lca(root, va, vb, result);
    
    	return result;
    }

// ② 节点不能是其自身的父节点(若B是A的孩子，A、B的最近共同父节点为A的父节点)：
    // 只要再增加一个变量保存父节点即可。
    static bool lca(const Node* root, const Node* va, const Node* vb, const Node* parrent, const Node*& result)
    {
    	bool left = false;
    
    	if (root->left != NULL)
    	{
    		left = lca(root->left, va, vb, root, result);
    		if (result) 
    			return false;
    	}
    
    	bool right = false;
    	if (root->right) 
    	{
    		right = lca(root-> right, va, vb, root, result);
    		if (result) 
    			return false;
    	} 
    
    	const int mid = (root == va) + (root == vb);
    	const int ret = left + right + mid;
    
    	if (ret == 2) 
    		result = (mid != 0 ? parrent : root);  
    
    	return (bool)ret;
    }
    
    const Node* lca(const Node* root, const Node* va, const Node* vb)
    {
    	const Node* result = NULL;
    	if (root) 
    		lca(root, va, vb, NULL, result);
    		
    	return result;
    }

4. 二叉树的广度遍历、逐层打印二叉树节点数据、只打印某层节点数据  
  
广度遍历可以用一个队列保存中间结果。每访问一个节点时，将不为空的的左右孩子分别放入队列中，然后从队列头部取出下一个节点，重复前面的操作直到队列为空。  
  
若需要对同一层的节点数据进行一些特殊操作（比如：打印完一层后换行、只打印某一层），可以记录某一层的最后一个节点，当遍历完该节点时（此时，队列的中的最后一个元素恰好就是下一层的最后一个节点），再进行这些特殊操作。

//简单的广度遍历
    void bfs(const Node* root)
    {
    	if (root == NULL) 
    		return;
    
    	std::deque<const Node*> dq;
    	while (true) 
    	{
    		if (root->left)
    		{
    			dq.push_back(root->left);
    		}
    		
    		if (root->right) 
    		{
    			dq.push_back(root->right);
    		}
    		
    		std::cout << root->data << " ";
    		
    		if (dq.empty()) 
    			break;
    
    		root = dq.front();
    		dq.pop_front();
    	}
    }
    
    //逐层打印 
    void bfs_level(const Node* root)
    {
    	if (root == NULL) 
    		return;
    
    	std::deque<const Node*> dq; 
    	const Node* end = root;
    
    
    	while (true) 
    	{
    		if (root->left != NULL)
    		{
    			dq.push_back(root->left);
    		}
    		if (root->right)
    		{
    			dq.push_back(root->right);
    		}
    
    		std::cout << root->data;
    		
    		if (root != end)
    		{
    			std::cout << " "; 
    		}
    		else 
    		{
    			std::cout << "\n";
    			if (dq.empty()) 
    			{
    				break;
    			}			
    			end = dq.back();
    		}
    		root = dq.front();
    		dq.pop_front();
    	}
    }
    
    //只打印某层
    void bfs_nth_level(const Node* root, int level) //root node is at level 0
    {
    	if (root == NULL || level < 0) 
    		return;
    
    	std::deque<const Node*> dq; 
    	const Node* end = root;
    	
    	while (true) 
    	{
    		if (root->left)
    		{
    			dq.push_back(root->left);
    		}
    		if (root->right)
    		{
    			dq.push_back(root->right);
    		}		
    
    		if (level == 0) 
    		{
    			std::cout << root->data << (root == end ? "\n" : " ");
    		}		
    		if (root == end) 
    		{
    			if (--level < 0 || dq.empty()) 
    			{
    				break;
    			}		
    			end = dq.back();
    		}
    
    		root = dq.front();
    		dq.pop_front();
    	}
    }

5. 在二叉树中找出和（叶子到根节点路径上的所有节点的数据和）为指定值的所有路径。  
  
要输出所有的路径，必须额外用一个栈来保存当前路径信息。  
  
当访问到节点A时，节点A的信息要在访问A的左右子树时用到，因而，该信息必须在遍历A的左右子树前加入到栈中，而在遍历完A的左右子树后从栈中移除。  
  
每访问一个节点，就计算当前路径值（可直接利用父节点的路径值），当其等于给定值且当前节点是叶子节点时，就打印路径信息。

static void node_path(const Node* root, const int value, int sum, std::deque<int>& dq)
    {
    	sum += root->data;
    	if (root->left == NULL && root->right == NULL) 
    	{
    		if (sum != value) 
    			return;
    
    
    		std::copy(dq.begin(), dq.end(), std::ostream_iterator<int>(std::cout, " "));
    		std::cout << root->data << "\n";
    		return;
    	}
    	
    	dq.push_back(root->data);
    	if (root->left) 
    	{
    		node_path(root->left, value, sum, dq);
    	}	
    	if (root->right)
    	{
    		node_path(root->right, value, sum, dq);
    	}
    
    	dq.pop_back();
    }
    
    void print_node_path(const Node *root, int value)
    {
    	if (root == NULL)
    		return;
    
    	std::deque<int> dq;
    	node_path(root, value, 0, dq);
    }
    
    //非递归解法
    void print_path_by_value(const Node *root, int value)
    {
    	typedef std::vector<const Node*> Container;
    	Container node;
    
    	node.reserve(64);
    	int sum = 0;
    	while (true) 
    	{
    		for ( ; root != NULL; root = root->left) 
    		{
    			sum += root->data;
    
    			if (sum == value && root->left == NULL && root->right == NULL) 
    			{
    				Container::const_iterator first = node.begin(), last = node.end();
    				for ( ; first != last; ++first) 
    				{
    					printf("%d ", (*first)->data);
    				}
    				
    				printf("%d\n", root->data);
    				sum -= root->data;
    
    				break;
    			}
    			node.push_back(root);	
    		}
    
    		while (true) 
    		{
    			if (node.empty()) 
    				return;
    
    			const Node* parrent = node.back();
    
    
    			if (root != parrent->right) 
    			{
    				root = parrent->right; break; 
    			}
    			root = parrent;
    			sum -= root->data;
    			node.pop_back();
    		}
    	}
    }

6. 将二叉查找树转为有序的双链表  
  
实际上就是对二叉查找树进行中序遍历。可以用两个变量分别保存刚访问的结点、新链表的头结点，访问某一个结点A时，设置该节点时left成员指向刚访问过的结点B，再设置结点B的right成员指向结点A。经过这样处理，得到的新双链表，除了头结点的left成员、尾结点的right成员没有设置外，其它的结点成员都被正确设置。而中序遍历的特点决定了第一个访问的数据节点的left成员一定为空指针，最后一个访问的数据节点的right成员也一定为空指针。因而不需要再对这两个成员进行额外的设置操作。

static void tree2list_inorder(Node* root, Node*& prev, Node*& list_head)
    {
    	if (root->left != NULL) 
    		tree2list_inorder(root->left, prev, list_head);
     
    	root->left = prev;
    
    	if (prev != NULL) 
    		prev->right = root;
    
    	prev = root;
    
    	if (list_head == NULL) 
    		list_head = root;
     
    	if (root->right != NULL)  
    		tree2list_inorder(root->right, prev, list_head);
    }
    
    
    Node* tree2list(Node* root)
    {
    	Node* list_head = NULL;
    	Node* prev = NULL;
    	if (root != NULL)
    	{
    		tree2list_inorder(root, prev, list_head);
    	}
    
    	return list_head;
    }

7. 求二叉树的镜像

// ① 在原来的二叉树上进行修改。
    static void mirror(Node* root)
    {
    	Node* const left = root->left;
    	Node* const right = root->right;
    
    
    	root->left = right;
    	root->right = left;  
    	
    	if (left) 
    	{
    		mirror(left);  
    	}
    
    
    	if (right)
    	{
    		mirror(right);  
    	}
    }
    
    
    Node* mirror_node(Node* root)
    {
    	if (root) 
    		mirror(root);
    		
    	return root;
    }
    
    
    // ② 创建一个二叉树的镜像，注意内存分配失败时的处理。
    static void clear_node(Node* root)
    {
    	Node* const left = root->left;
    	Node* const right = root->right;
    	delete root;
    
    	if (left) 
    		clear_node(left);
    
    	if (right) 
    		clear_node(right);
    }
    
    static void clone_mirror(const Node* root, Node*& position)
    {
    	Node *node = new Node;
    	*node = *root;
    	position = node;
    
    	if (root->left) 
    		clone_mirror(root->left, node->right);
    
    	if (root->right)
    		clone_mirror(root->right, node->left);
    }
    
    
    Node* clone_mirror(const Node* root)
    {
    	Node* new_root = NULL;
    
    	if (root) 
    	{
    		try 
    		{
    			clone_mirror(root, new_root);
    		}
    		catch (...) 
    		{
    			if (new_root) 
    				clear_node(new_root);
    			new_root = NULL;
    		}     
    	}
    	
    	return new_root;
    }

8. 二叉树前序、中序、后序遍历的非递归实现  
  
三种遍历相同点是：从某节点出发向左走到头(边走边记录访问过的节点)，然后退回到该节点，再进入右子树，再重复前面操作。  
  
① 对前序遍历，先访问节点数据、以后再访问该节点右孩子的数据，因而可以不记录该节点，而直接记录该节点的右孩子。  
② 对前序、中序遍历，同一个节点可能要被访问两次：从上往下、（沿着左子树）从下往上。  
③ 对后序遍历，同一个节点可能要被访问三次：从上往下、（沿着左子树）从下往上、（沿着右子树）从下往上。  
  
后序遍历相对麻烦的地方是：从下往上时，要判断是沿着左子树向上，还是沿着右子树向上，若是后者（或父节点的右孩子为空节点）才访问父节点数据。方向的判断，只须判断当前节点是否是其父节点的右孩子,不需要对每个结点都设一个标志！另外，若当前节点是某个叶子节点的左孩子（此时当前节点是空节点），可以把当前节点当作是该叶子节点的右孩子处理，而不影响结果。

void preorder(const Node* root)
    {
    	std::deque<const Node*> dq;
    	while (true) 
    	{
    		while (root) 
    		{
    			std::cout << root->data << " "; 
    			if (root->right) 
    				dq.push_back(root->right);
    			
    			root = root->left;
    		}
    
    
    		if (dq.empty()) 
    			break;
    
    
    		root = dq.back();
    		dq.pop_back();
    	}
    }
    
    
    void inorder(const Node* root)
    {
    	std::deque<const Node*> dq;
    	while (true) 
    	{
    		for ( ; root != NULL; root = root->left) 
    		{
    			dq.push_back(root);
    		}
    
    
    		if (dq.empty())
    		{
    			break;
    		}
    		
    		root = dq.back();
    		dq.pop_back();
    
    
    		std::cout << root->data << " "; 
    		root = root->right;
    	}
    }
    
    
    void postorder(const Node* root)
    {
    
    
    	std::deque<const Node*> dq;
    	while (true) 
    	{
    		for ( ; root != NULL; root = root->left) 
    			dq.push_back(root);
    
    
    		while (true) 
    		{
    			if (dq.empty()) return;
    			const Node* parrent = dq.back();
    			//可以不检查parrent->right是否为空指针
    			const Node* right = parrent->right;
    			if (right && root != right) 
    			{
    				root = right; 
    				break;
    			}
    
    
    			std::cout << parrent->data << " ";
    			root = parrent;
    			dq.pop_back();
    		}
    	}
    }

9.计算二叉树高度的非递归实现  
  
计算二叉树的高度，一般都是用后序遍历，先算出左子树的高度，再算出右子树的高度，最后取较大者。但若直接将该算法改成非递归形式是非常麻烦的。考虑到二叉树高度与深度的关系，可以有下面两种方法：  
  
① 先将算法改成前序遍历再改写非递归形式。前序遍历算法：遍历一个节点前，先算出当前节点是在哪一层，层数的最大值就等于二叉树的高度。  
  
② 修改上面提到的后序遍历迭代写法，上面的代码中，所用到辅助栈（或双端队列），其大小达到的最大值减去1 就等于二叉树的高度。因而只须记录在往辅助栈放入元素后（或者在访问结点数据时），辅助栈的栈大小达到的最大值。

int tree_height_preorder(const Node* root)
    {
    
    
    	struct Info 
    	{
    		const Node* node;
    		int level;
    	};
    
    
    	std::deque<Info> dq;
    	int level = -1;
    	int height = -1;
    
    
    	while (true) 
    	{
    		while (root) 
    		{
    			++level;     
    			if (root->right) 
    			{
    				Info info = {root->right, level};
    				dq.push_back(info);
    			}
    			root = root->left;
    		}
    		height = max(height, level);
    		if (dq.empty()) 
    			break;
    
    
    		const Info& info = dq.back();
    		root = info.node;
    		level = info.level;
    		dq.pop_back();
    	}
    	
    	return height;
    }
    
    
    int tree_height_postorder(const Node* root)
    {
    	std::deque<const Node*> dq;
    	int height = -1;
    	while (true) 
    	{
    		for ( ; root != NULL; root = root->left) 
    			dq.push_back(root);
    
    
    		height = max(height, (int)dq.size() - 1);
    		
    		while (true) 
    		{
    			if (dq.empty()) return height;
    			const Node* parrent = dq.back();
    			//可以不检查parrent->right是否为空指针
    			const Node* right = parrent->right;
    			if (right && root != right) 
    			{
    				root = right; 
    				break;
    			}
    			root = parrent;
    			dq.pop_back();
    		}
    	}
    }

10 连接二叉树同一层上的结点  
若二叉树结构定义为：  
  
struct Node \{  
Node \*left;  
Node \*right;  
Node \*right\_sibling; //  
int data;  
\};  
  
  
其中，right\_sibling指向同一层上右侧的第一个结点（没有的话则设为空指针）。  
  
要求设置各结点的right\_sibling成员（其它成员已经初始化）。  
  
本题可以用递归，也可以使用迭代，两种方法都是时间复杂度O(n)，空间复杂度O(1)（递归解法可能会栈溢出）。  
  
递归法：访问一个结点前，事先算出它的right\_sibling。访问该结点时，利用该结点的right\_sibling指针，算出其左右孩子的right\_sibling（找出该结点右侧第一个不是叶子的结点B,结点B的某个孩子，就是该结点某个孩子的right\_sibling）。需要特别注意的是：访问二叉树可以采用前序遍历，要先访问右子树，再访问左子树，这样可以保证访问到某个结点，该结点及其右侧的结点的right\_sibling指针已被正确设置。  
  
迭代法：访问某一层前，先设置好该层所有节点的right\_sibling，访问该层时，利用已经设置好的right\_sibling信息，设置下一层节点的right\_sibling。

//递归解法：
    static void set_sibling(Node* root, Node* sibling)
    {
    	root->right_sibling = sibling;
    
    
    	Node* const left = root->left;
    	Node* const right = root->right;
    
    
    	if (left == NULL && right == NULL) 
    		return;
    
    
    	while (sibling) 
    	{
    		if (sibling->left) 
    		{
    			sibling = sibling->left; break;
    		}
    
    
    		if (sibling->right) 
    		{
    			sibling = sibling->right; 
    			break;
    		}
    
    
    		sibling = sibling->right_sibling;
    	}
    
    
    	if (right != NULL) 
    	{
    		set_sibling(right, sibling); 
    		sibling = right;
    	} 
    
    
    	if (left != NULL) 
    		set_sibling(left, sibling);
    }
    
    
    void set_sibling(Node* root)
    {
    	if (root) 
    		set_sibling(root, NULL);
    }
    
    
    //非递归解法：
    void set_right_sibling2(Node* root)
    {
    
    
    	if (root == NULL) 
    		return;
    
    
    	root->right_sibling = NULL;
    	Node* level_start = NULL;
    	while (root != NULL) 
    	{
    		Node* const left = root->left;
    		Node* const right = root->right;
    		if (level_start == NULL) 
    				level_start = (left ? left : right);
    
    
    		Node* right_sibling = NULL;
    
    
    		while (1) 
    		{
    			root = root->right_sibling;
    			if (root == NULL) 
    			{
    				root = level_start; 
    				level_start = NULL; 
    				break; 
    			}
    
    
    			if (root->left)   
    			{ 
    				right_sibling = root->left; 
    				break;
    			}
    
    
    			if (root->right) 
    			{
    				right_sibling = root->right; 
    				break;
    			}
    		}
    		if (right != NULL) 
    		{
    			right->right_sibling = right_sibling; 
    			right_sibling = right; 
    		}
    
    
    		if (left != NULL) 
    		{
    			left->right_sibling = right_sibling;
    		}
    	}	
    }

[http_www.cppblog.com_flyinghearts_archive_2012_02_28_166713.html_Toc317966395]: http://www.cppblog.com/flyinghearts/archive/2012/02/28/166713.html#_Toc317966395