关于常见的各种二叉树算法题C++代码实现（希望可以持续更新…）

• 1、定义一颗二叉树
• 2、二叉树的前序、中序、后序遍历
• 3、已知二叉树的前序和中序遍历还原二叉树
• 4、二叉树的层序遍历
• 5、判断是否为平衡二叉树

struct TreeNode {
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

NC45 实现二叉树先序，中序和后序遍历

核心：遍历时第一次遇到则记录（前），第二次遇到则记录（中），第三次遇到则记录（后）

特性：前序（根+左子树+右子树）、中序（左子树+根+右子树）、后序（左子树+右子树+根）

vector firstOrders(TreeNode* root, vector& vec) {
	if (root == nullptr) {
		return vec;
	}
	vec.push_back(root->val);
	firstOrders(root->left, vec);
	firstOrders(root->right, vec);
	return vec;
}

vector secondOrders(TreeNode* root, vector& vec) {
	if (root == nullptr) {
		return vec;
	}
	secondOrders(root->left, vec);
	vec.push_back(root->val);
	secondOrders(root->right, vec);
	return vec;
}

vector thirdOrders(TreeNode* root, vector& vec) {
	if (root == nullptr) {
		return vec;
	}
	thirdOrders(root->left, vec);
	thirdOrders(root->right, vec);
	vec.push_back(root->val);
	return vec;
}


vector > threeOrders(TreeNode* root) {
	vector > ret_v;
	if (root == nullptr) {
		ret_v = { {}, {}, {} };
		return ret_v;
	}
	vector cur_v1;
	cur_v1 = firstOrders(root, cur_v1);
	ret_v.push_back(cur_v1);

	vector cur_v2;
	cur_v2 = secondOrders(root, cur_v2);
	ret_v.push_back(cur_v2);

	vector cur_v3;
	cur_v3 = thirdOrders(root, cur_v3);
	ret_v.push_back(cur_v3);

	return ret_v;
}

NC12 重建二叉树

TreeNode* reConstructBinaryTree(vector pre, vector vin) {
	if (pre.empty() || vin.empty() || pre.size() != vin.size()) {
		return  nullptr;
	}
	int index = 0;
	TreeNode* pRoot = new TreeNode(pre[0]);
	vector left_pre;
	vector left_vin;
	vector right_pre;
	vector right_vin;
	for (size_t i = 0; i < vin.size(); ++i) {
		if (vin[i] == pre[0]) {
			index = i;
			break;
		}
	}
	for (int i = 0; i < index; ++i) {
		left_pre.push_back(pre[i + 1]);
		left_vin.push_back(vin[i]);
	}
	for (int i = index + 1; i < (int)vin.size(); ++i) {
		right_pre.push_back(pre[i]);
		right_vin.push_back(vin[i]);
	}
	pRoot->left = reConstructBinaryTree(left_pre, left_vin);
	pRoot->right = reConstructBinaryTree(right_pre, right_vin);
	return pRoot;
}

NC15 求二叉树的层序遍历

vector > levelOrder1(TreeNode* root) {
	vector> v;
	if (root == nullptr) {
		return v;
	}
	queue q;
	q.push(root);
	while (!q.empty()) {
		vector cur_v;
		size_t size = q.size();
		while (size > 0) {
			TreeNode* node = q.front();
			q.pop();
			cur_v.push_back(node->val);
			if(node->left != nullptr){
				q.push(node->left);
			}
			if (node->right != nullptr) {
				q.push(node->right);
			}
			size--;
		}
		if (cur_v.size() > 0) {
			v.push_back(cur_v);
		}
	}
	return v;
}

NC62 判断是不是平衡二叉树

所谓平衡二叉树就是左右子树的高度相差不大于一即可~~

int height(TreeNode* root) {
	if (root != nullptr) {
		return max(height(root->left), height(root->right)) + 1;
	}
	return 0;
}

bool IsBalanced_Solution(TreeNode* pRoot) {
	if (pRoot == nullptr) {
		return true;
	}
	int left_h = height(pRoot->left);
	int right_h = height(pRoot->right);
	int num = left_h - right_h;
	if (num > 1 || num < -1) {
		return false;
	}
	return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
}