代码随想录 第八章 二叉树02

纸上得来终觉浅，觉知此事要躬行

8、二叉数的最大深度

leetcode104：二叉数的最大深度

求一棵二叉树的最大深度，跟节点的深度为1.

（1）、递归法

因为要通过递归函数的返回值计算树的高度，所以本题需要使用后序遍历（左->右->中）。

先求左子树的深度，再求右字树的深度，最后取左右深度中的最大值再加1。就是当前节点为跟节点的树的深度。

int GetMaxDepth(BitNode* root) {
	if (root == nullptr) {
		return 0;
	}
	int leftdepth = GetMaxDepth(root->lchild);
	int rightdepth = GetMaxDepth(root->rchild);
	return max(leftdepth, rightdepth) + 1;
}

（2）、迭代法

在二叉树中，一层一层地遍历二叉树，遍历的层数就是二叉树的深度，如果使用迭代法，那么使用层序遍历是最合适的。

int GetMaxDepthIter(BitNode* root) {
	if (root == nullptr) {
		return 0;
	}
	queue que;
	que.push(root);
	int depth = 0;
	while (!que.empty()) {
		int size = que.size();
		for (int i = 0; i < size; i++) {
			BitNode* node = que.front();
			que.pop();
			if (node->lchild != nullptr) {
				que.push(node->lchild);
			}
			if (node->rchild != nullptr) {
				que.push(node->rchild);
			}
			
		}
		depth++;
	}
	return depth;
}

9、二叉树的最小深度

leetcode111：

求一棵二叉树的最小深度，根节点的深度为1.

最小深度，从根节点到最近叶子节点的最短路径上的节点数量。

遍历顺序依然是后序遍历（因为要比较递归返回之后的结果），但在处理中间节点的逻辑上，最大深度很容易理解，而最小深度容易有一个误区。

注意：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。左右孩子都为空的节点才是叶子节点。

如果右子树为空，左子树不为空，则最小深度是左子树的深度+1。如果左子树为空，右子树不为空，则说明最小深度是右子树的深度+1。如果左右字树都不为空，那么返回左右字树深度的最小值+1。

可以看出：求二叉树最小深度和求二叉树最大深度的差别主要在于处理左右孩子不为空的逻辑。

递归法：

int GetMinDepth(BitNode* root) {
	if (root == nullptr) {
		return 0;
	}
	int leftdepth = GetMinDepth(root->lchild);
	int rightdepth = GetMinDepth(root->rchild);
	if (root->lchild != nullptr && root->rchild == nullptr) {
		return 1 + leftdepth;
	}
	if (root->lchild == nullptr && root->rchild != nullptr) {
		return 1 + rightdepth;
	}
	return 1 + min(leftdepth, rightdepth);
}

迭代法：

本题还可以使用层序遍历的方式解答，需要注意的是，只要当左右孩子都为空的时候，才能说明遍历到最低点了。如果其中一个孩子为空则不是最低点。

int GetMinDepthIter(BitNode* root) {
	if (root == nullptr) {
		return 0;
	}
	queue que;
	que.push(root);
	int depth = 0;
	while (!que.empty()) {
		int size = que.size();
		depth++;
		for (int i = 0; i < size; i++) {
			BitNode* node = que.front();
			que.pop();
			if (node->lchild != nullptr) {
				que.push(node->lchild);
			}
			if (node->rchild != nullptr) {
				que.push(node->rchild);
			}
			if (node->lchild == nullptr && node->rchild == nullptr) {
				return depth;
			}
		}
	}
	return depth;
}

10、平衡二叉树

leetcode110：平衡二叉树

每一个节点的左子树和右字树的高度差的绝对值不超过1.

二叉树节点的深度：从根节点到该节点的最长简单路径的条数（或者节点数）。

二叉树节点的高度：从该节点到叶子节点的最长简单路径的条数（或者节点数）。

求高度和求深度所用的遍历方式是不一样的，求深度要从上到下去查找，所以需要前序遍历，而高度只能从下到上去查找，所以需要后序遍历。

递归法：

如果求二叉树的高度，则该使用后序遍历。

int GetDepth(BitNode* root) {
	if (root == nullptr) {
		return 0;
	}
	int leftdepth = GetDepth(root->lchild);
	if (leftdepth == -1) {
		return -1;
	}
	int rightdepth = GetDepth(root->rchild);
	if (rightdepth == -1) {
		return -1;
	}
	return abs(leftdepth - rightdepth) > 1 ? -1 : 1 + max(leftdepth, rightdepth);
}

11、二叉树的所有路径

leetcode257：

给出一个二叉树，返回所有根节点到叶子节点的路径。

说明：叶子节点是指没有子节点的节点。

递归和回溯要永远在一起！！！！！

递归和回溯要永远在一起！！！！！

递归和回溯要永远在一起！！！！！

这道题目是求从根节点到叶子节点的所有路径，所以需要使用前序遍历，这样才方便让父节点指向子节点，找到对应的路径。在这道题目中将正式涉及回溯，因为我们要记录路径，需要回溯操作来回退一条路径从而进入另一个路径。

class Solution {
 private:
	vector result;
	vector<int> path;
 
 private:
	void TraveSal(BitNode* root,vector<int>& path,vector& result) {
		path.push_back(root->data);
		if (root->lchild == nullptr && root->rchild == nullptr) {
			string spath;
			for (int i = 0; i < path.size(); i++) {
				spath += to_string(path[i]);
				spath += "->";
			}
			spath+= to_string(path[path.size()-1]);
			result.push_back(spath);
			return;
		}
		if (root->lchild != nullptr) {
			TraveSal(root->lchild, path, result);
			path.pop_back();
		}
		if (root->rchild != nullptr) {
			TraveSal(root->rchild, path, result);
			path.pop_back();
		}
	}
 public:
	vector BinaryTreePaths(BitNode* root) {
		vector result;
		vector<int>path;
		if (root == nullptr) {
			return result;
		}
		TraveSal(root, path, result);
		return result;
	}
};

上述代码充分体现了回溯算法的特点，版本一的代码还可以精简成如下的代码。

class Solution {
 private:
	vector result;
	string path;
 
 private:
	void TraveSal(BitNode* root,string path,vector& result) {
		path += to_string(root->data);
		if (root->lchild == nullptr && root->rchild == nullptr) {
			result.push_back(path);
			return;
		}
		if (root->lchild != nullptr) {
			TraveSal(root->lchild, path + "->", result);
		}
		if (root->rchild != nullptr) {
			TraveSal(root->rchild, path + "->", result);
		}
	}
 public:
	vector BinaryTreePaths(BitNode* root) {
		vector result;
		string path;
		if (root == nullptr) {
			return result;
		}
		TraveSal(root, path, result);
		return result;
	}
};

把path+"->"作为函数参数，因为并没有改变path的数值，执行完递归函数之后，path依然是之前的数值（相当于回溯了）。

迭代法：

模拟递归过程除了需要一个栈，还需要一个栈来存放对应的遍历路径。

vector BianeryTreePaths(BitNode* root) {
	stack st;
	stack pathst;
	vector result;
	if (root == nullptr) {
		return result;
	}
	st.push(root);
	pathst.push(to_string(root->data));
	while (!st.empty()) {
		BitNode* node = st.top();
		st.pop();
		string path = pathst.top();
		pathst.pop();
		if (root->lchild == nullptr && root->rchild == nullptr) {
			result.push_back(path);
		}
		if (root->rchild != nullptr) {
			st.push(root->rchild);
			pathst.push(path + "->" + to_string(root->rchild->data));
		}
		if (root->rchild != nullptr) {
			st.push(root->lchild);
			pathst.push(path + "->" + to_string(root->lchild->data));
		}
	}
	return result;
}

12、路径总和

leetcode112

找到一条从根节点到叶子节点的路径，使这个路径的节点总和等于目标值。

这道题要我们遍历从根节点到叶子节点的路径，计算总和是不是目标和。

（1）、递归法

可以使用深度优先遍历的方式。

bool HasPathSum(BitNode* root, int count) {
	if (root->lchild == nullptr && root->rchild == nullptr &&
		  count == 0) {
		return true;
	}
	if (root->lchild == nullptr && root->rchild == nullptr) {
		return false;
	}
	if (root->lchild != nullptr) {
		if (HasPathSum(root->lchild, count - root->lchild->data)) {
			return true;
		}
	}
	if (root->rchild != nullptr) {
		if (HasPathSum(root->rchild, count - root->rchild->data)) {
			return true;
		}
	}
	return false;
}

（2）、迭代法

如果使用栈模拟递归，那么如何实现回溯呢？

此时栈内的一个元素不仅要记录该节点指针，还要记录从头节点的路径数值的总和。

如果是c++，则用pair的结构存放这个栈内的元素。将栈内的一个元素定义为pair

pair<节点指针，路径数值>。

bool HashPathSumIter(BitNode* root, int sum) {
	if (root == nullptr) {
		return false;
	}
	stackint>> st;
	st.push(pairint>(root, root->data));
	while (!st.empty()) {
		pairint> node = st.top();
		st.pop();
		if (node.first->lchild == nullptr && node.first->rchild == nullptr &&
			  node.second == sum) {
			return true;
		}
		if (node.first->rchild != nullptr) {
			st.push(pairint>(node.first->rchild,
				node.second + node.first->rchild->data));
		}
		if (node.first->lchild != nullptr) {
			st.push(pairint>(node.first->lchild,
				node.second + node.first->lchild->data));
		}
	}
	return false;
}

12、路径总和||

leetcode113：找到所有从根节点到叶子节点的路径，使这些路径的节点总和等于目标值。

如果需要搜索整课二叉树且不用处理递归函数的返回值，则递归函数就不需要返回值。

递归和回溯要永远在一起！

递归和回溯要永远在一起！

递归和回溯要永远在一起！

class Solution {
 private:
	vectorint>> result;
	vector<int> path;
 private:
	void TraverSal(BitNode* root, int count) {
		if (root->lchild == nullptr && root->rchild == nullptr &&
			  count == 0) {
			result.push_back(path);
			return;
		}
		if (root->lchild == nullptr && root->rchild == nullptr) {
			return;
		}
		if (root->lchild != nullptr) {
			path.push_back(root->lchild->data);
			count -= root->lchild->data;
			TraverSal(root->lchild, count);
			count += root->lchild->data;
			path.pop_back();
		}
		if (root->rchild != nullptr) {
			path.push_back(root->rchild->data);
			count -= root->rchild->data;
			TraverSal(root->rchild, count);
			count += root->rchild->data;
			path.pop_back();
		}
	}
 public:
	vectorint>> HashPathSum1(BitNode* root, int count) {
		result.clear();
		path.clear();
		if (root == nullptr) {
			return result;
		}
		path.push_back(root->data);
		count -= root->data;
		TraverSal(root, count);
		return result;
	}
};

13、构造一棵树

1、使用中序与后序遍历构造二叉树

leetcode106：使用中序和后序遍历构造二叉树

给出中序遍历和后序遍历的两个数组（没有重复元素），通过这两个数组构造一棵二叉树。

根据两个遍历顺序构造一个唯一的二叉树的原理：以后序数组的最后一个元素作为切割点，先切割中序数组，然后根据中序数组，反过来再切割后序数组。一层一层切下去，每次后序数组的最后一个元素就是节点元素。

根据中序遍历数组和后序遍历数组画一棵二叉树。

那么代码应该怎么写呢？

说到一层一层切割，就应该想到递归。

第一步：如果数组长度为零，则说明是空节点。

第二步：如果数组不为空，那么将后序数组的最后一个元素作为节点元素。

第三步：找到后序数组的最后一个元素在中序数组中的位置并将其作为切割点。

第四步：切割中序数组，切割成中序左数组和中序右数组（一定是先切割中序数组）。

第五步：切割后序数组，切成后序左数组和后序右数组。

第六步：递归处理左区间和右区间。

难点就是如何切割数组，以及找到边界值。

此时应该确定切割的标准，是左闭右开、左开右闭，还是左闭右闭，这个标准是不变量，要在递归过程中保持不变量不变化。

在切割的过程中会产生四个区间，如果把握不好不变量，一会儿左闭右开，一会儿左闭右闭，那么代码逻辑就会陷入混乱。

为什么先切割中序数组呢？

切割点是后序数组的最后一个元素，基于这个元素来切割中序数组，所以必须先切割中序数组。中序数组相对比较好切，找到切割点（后序数组的最后一个元素），然后切割，坚持左闭右开的标准。

接下来就要切割后序数组了。

首先后序数组的最后一个元素一定不考虑，因为这个元素即是切割点，又是当前二叉树中间节点的元素。

怎么查找后序数组的切割点呢？

后序数组不像中序数组那样有明确的切割点，此时有一个关键点，就是中序数组的长度一定和后序数组的长度相同。

既然中序数组可以切成左中序数组和右中序数组，那么后序数组也可以按照左中序数组的长度进行切割，切割成左后序数组和右后序数组。

class Solution {
 private:
	BitNode* TraverSal(vector<int>& inorder, vector<int>& postorder) {
		int rootvalue = postorder[postorder.size() - 1];
		BitNode* root = new BitNode(rootvalue);
		if (postorder.size() == 1) {
			return root;
		}
		int delimiterindex = 0;
		for (delimiterindex = 0; delimiterindex < inorder.size(); delimiterindex++) {
			if (inorder[delimiterindex] == rootvalue) {
				break;
			}
		}
		//切割中序遍历
		//左闭右开区间[0,delimiterindex）
		vector<int> leftinorder(inorder.begin(), inorder.begin()+ delimiterindex);
		vector<int> rightinorder(inorder.begin() + delimiterindex + 1, inorder.end());
		//切割后序遍历
		//舍弃末尾元素
		postorder.resize(postorder.size() - 1);
		vector<int>leftpostorder(postorder.begin(), postorder.begin() + leftinorder.size());
		vector<int>rightpostorder(postorder.begin() + leftinorder.size(), postorder.end());
		root->lchild = TraverSal(leftinorder, leftpostorder);
		root->rchild = TraverSal(rightinorder, rightpostorder);
		return root;
	}
 public:
	BitNode* BuildTree(vector<int>& inorder, vector<int>& postorder) {
		if (inorder.size() == 0 || postorder.size() == 0) {
			return nullptr;
		}
		return TraverSal(inorder, postorder);
	}
};
 
void main() {
	
	vector<int> inorder ={8,4,15,12,7};
	vector<int> postorder = {8,15,7,12,4};
	Solution solu;
	BitNode* ret = solu.BuildTree(inorder, postorder);
 
	cout << "hello world" << endl;
}

细心的读者会发现上述代码的性能并不好，因为每次递归定义了新的vector，即耗时又耗费空间。

14、使用前序与中序遍历构造二叉树

leetcode105：使用前序与中序序列构造二叉树

class Slotion {
 private:
	BitNode* TraverSal(vector<int>& inorder, vector<int>& preorder) {
		if (preorder.size() == 0) {
			return nullptr;
		}
		int rootvalue = preorder[0];
		BitNode* root = new BitNode(rootvalue);
		if (preorder.size() == 1) {
			return root;
		}
		//第三步，查找切割点
		int delimiterindex = 0;
		for (delimiterindex = 0; delimiterindex < inorder.size(); delimiterindex++) {
			if (inorder[delimiterindex] == rootvalue) {
				break;
			}
		}
		//第四步：切割中序数组 左闭右开区间
		vector<int> leftinorder(inorder.begin(), inorder.begin() + delimiterindex);
		vector<int> rightinorder(inorder.begin() + delimiterindex + 1, inorder.end());
 
		//第五步：调整前序数组，移除第一个元素
		preorder.erase(preorder.begin());
		//第六步，切割前序数组 左闭右开区间
		vector<int> leftpreorder(preorder.begin(), preorder.begin() + leftinorder.size());
		vector<int> rightpreorder(preorder.begin() + leftinorder.size(), preorder.end());
 
		root->lchild = TraverSal(leftinorder, leftpreorder);
		root->rchild = TraverSal(rightinorder, rightpreorder);
		return root;
	}
 public:
	BitNode* BuildTree(vector<int>& inorder, vector<int>& preorder) {
		if (inorder.size() == 0 || preorder.size() == 0) {
			return nullptr;
		}
		return TraverSal(inorder, preorder);
	}
};

前序数组和中序数组可以唯一确定一棵二叉树，后序数组和中序数组也可以唯一确定一颗二叉树，那么前序数组和后序数组可不可以唯一确定一颗二叉树呢？

前序数组和后序数组不能唯一确定一颗二叉树，这是因为没有中序遍历就无法确定左右区间，即无法确定分割点。

15、合并·两棵树

leetcode617:合并两棵树

其实和遍历一颗树的逻辑是一样的，只不过递归函数需要传入两棵树的根节点来进行合并操作。

（1）、递归法

针对二叉树使用递归法，就要考虑使用前、中、后序哪种遍历方式。

因为传入了两棵树，所以判断两棵树遍历的节点t1和t2，如果t1为null，那么两个节点合并后就应该是t2，如果t2为null，那两棵树合并之后就应该是t1（如果t1也为null，那么合并之后就是null）。

这里可以重复使用t1这颗树，t1就是合并之后树的根节点（修改了原来树的结构）。

BitNode* MergerTrees(BitNode* t1, BitNode* t2) {
	if (t1 == nullptr) {
		return t2;
	}
	if (t2 == nullptr) {
		return t1;
	}
	t1->data = t1->data + t2->data;
	t1->lchild = MergerTrees(t1->lchild, t2->lchild);
	t1->rchild = MergerTrees(t1->rchild, t2->rchild);
	return t1;
}

（2）、迭代法

具体思路，处理二叉树对称的时候就把两棵树的节点同时加入队列进行比较。

BitNode* MergerTreesIter(BitNode* t1, BitNode* t2) {
	queueque;
	que.push(t1);
	que.push(t2);
	while (!que.empty()) {
		BitNode* node1 = que.front(); que.pop();
		BitNode* node2 = que.front(); que.pop();
		node1->data = node1->data + node2->data;
		//如果两棵树的左节点都不为空，则加入队列；
		if (node1->lchild != nullptr && node2->lchild != nullptr) {
			que.push(node1->lchild);
			que.push(node2->lchild);
		}
		//如果两棵树的右节点都不为空，则加入队列；
		if (node1->rchild != nullptr && node2->rchild != nullptr) {
			que.push(node1->rchild);
			que.push(node2->rchild);
		}
		if (node1->lchild == nullptr && node2->lchild != nullptr) {
			node1->lchild = node2->lchild;
		}
		if (node1->rchild == nullptr && node2->rchild != nullptr) {
			node1->rchild = node2->rchild;
		}
	}
	return t1;
}